droite|vignette|Un Conus textile, présentant des motifs similaires à ceux de la règle 30.
La règle 30 est un automate cellulaire élémentaire introduit par Stephen Wolfram en 1983. Il a la particularité de produire des motifs complexes, d'apparence aléatoire, à partir de règles simples et déterministes.
Définition La règle 30 est un automate cellulaire dit élémentaire : il consiste en une grille unidimensionnelle de cellules ne pouvant prendre que deux états, 0 et 1, avec un voisinage constitué, pour chaque cellule, d'elle-même et des deux cellules qui lui sont adjacentes. La règle locale de transition est donnée par le tableau suivant :
Motif initial (t)111110101100011010001000Valeur suivante de la cellule centrale (t+1)00011110
Le numéro 30 provient de son écriture binaire 30 = 00011110 correspondant à la seconde ligne du tableau.
Propriétés
Le nombre de cellules dans l'état 1 à la n-ième génération en partant de la configuration initiale où une seule cellule est dans l'état 1 donne la suite 1, 3, 3, 6, 4, 9, 5, 12, 7, 12… (). La structure qui résulte de cette évolution de l'automate présente plusieurs motifs, comme l'apparition fréquente de triangles de cellules dans l'état 0 (en blanc dans les illustrations ci-dessus), ainsi qu'un motif rayé sur le côté gauche.
Au-delà du comportement visuellement chaotique de la règle 30, il a été prouvé qu'elle vérifiait également une définition plus rigoureuse du chaos pour les systèmes dynamiques à temps discret.
Applications La règle 30 a été proposée pour servir de générateur de nombres pseudo-aléatoires ainsi que de méthode de chiffrement de flux. vignette|Photographie de la , décorée avec un motif obtenu avec la règle 30. La est décorée avec un motif obtenu avec la règle 30 (ou plus précisément avec la règle 135, pour laquelle les états sont inversés par rapport à la règle 30).
Notes et références
Catégorie:Automate cellulaire