Règle 30
La règle 30 est un automate cellulaire élémentaire introduit par Stephen Wolfram en 1983[2],[3]. Il a la particularité de produire des motifs complexes, d'apparence aléatoire, à partir de règles simples et déterministes.
Définition
[modifier | modifier le code]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[4] :
| Motif initial (t) | 111 | 110 | 101 | 100 | 011 | 010 | 001 | 000 |
|---|---|---|---|---|---|---|---|---|
| Valeur suivante de la cellule centrale (t+1) | 0 | 0 | 0 | 1 | 1 | 1 | 1 | 0 |
Le numéro 30 provient de son écriture binaire 30 = 000111102 correspondant à la seconde ligne du tableau.
Propriétés
[modifier | modifier le code]-
Évolution de l'automate à partir de la configuration initiale où une seule cellule est dans l'état 1 (noir).
-
256 premières étapes de l'automate, avec la même configuration initiale.
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… (suite A070952 de l'OEIS). 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[5].
Applications
[modifier | modifier le code]La règle 30 a été proposée pour servir de générateur de nombres pseudo-aléatoires[6] ainsi que de méthode de chiffrement de flux[7].
La gare de Cambridge North (en) 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)[8].
Notes et références
[modifier | modifier le code]- (en) Stephen Coombes, « The Geometry and Pigmentation of Seashells », University of Nottingham, (lire en ligne)
- (en) Stephen Wolfram, « Statistical mechanics of cellular automata », Reviews of Modern Physics, vol. 55, no 3, , p. 601–644 (DOI 10.1103/RevModPhys.55.601, lire en ligne, consulté le )
- (en) Eric W. Weisstein, « Rule 30 », sur mathworld.wolfram.com (consulté le )
- (en) Erica Jen, « Aperiodicity in one-dimensional cellular automata », Physica D: Nonlinear Phenomena, vol. 45, no 1, , p. 3–18 (ISSN 0167-2789, DOI 10.1016/0167-2789(90)90169-P, lire en ligne, consulté le )
- (en) Gianpiero Cattaneo, Michele Finelli et Luciano Margara, « Investigating topological chaos by elementary cellular automata dynamics », Theoretical Computer Science, vol. 244, no 1, , p. 219–241 (ISSN 0304-3975, DOI 10.1016/S0304-3975(98)00345-4, lire en ligne, consulté le )
- (en) « Random Number Generation—Wolfram Language Documentation », sur reference.wolfram.com (consulté le )
- (en) Willi Meier et Othmar Staffelbach, « Analysis of Pseudo Random Sequences Generated by Cellular Automata », Advances in Cryptology — EUROCRYPT ’91, Springer, , p. 186–199 (ISBN 978-3-540-46416-7, DOI 10.1007/3-540-46416-6_17, lire en ligne, consulté le )
- (en) « Oh My Gosh, It’s Covered in Rule 30s!—Stephen Wolfram Writings », sur writings.stephenwolfram.com, (consulté le )
