Règle 30
# 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) | 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 = $00011110_2$ correspondant à la seconde ligne du tableau.

## Propriétés

* É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.

## 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.

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).

