Rule 30 produit une dynamique chaotique à partir d’une règle binaire

Principe de la règle

Rule 30 appartient aux 256 automates cellulaires élémentaires. Chaque cellule regarde les trois cellules situées au rang précédent (gauche, centre, droite) et, selon la combinaison, adopte une couleur noire ou blanche. Les huit réponses sont codées sous forme binaire : 00011110, ce qui correspond au numéro 30. Ainsi, la règle est entièrement décrite par ce nombre : aucune autre donnée n’est requise pour générer l’évolution complète du système.

Comportement aléatoire et enjeux

Stephen Wolfram a montré dans les années 1980 que, contrairement à la plupart des automates qui s’éteignent ou se stabilisent, Rule 30 produit un motif dont le côté droit ne se stabilise jamais et dont la colonne centrale réussit les tests standards de génération aléatoire. Cette propriété a été exploitée pendant plusieurs années pour fournir les nombres aléatoires de Mathematica. En 2019, Wolfram a annoncé un prix de 30 000 $, réparti en trois questions portant sur la colonne centrale ; aucune des réponses n’a encore été démontrée, même après le calcul d’un milliard de cellules qui restent visuellement aléatoires.

Ordre aux bords et limites connues

Les deux bords du triangle présentent des structures déterministes. Le bord gauche forme des bandes rayées qui s’étendent le long d’une ligne dont la pente moyenne est de 0,244 carré par rang, proche de la vitesse de propagation (0,246) d’une perturbation du côté droit vers la gauche. Cette ligne a été suivie jusqu’à la rangée 524 288, où elle se comporte comme une marche aléatoire autour de la droite. Le bord droit montre, à chaque rang pair, un triangle blanc dont la largeur dépend du nombre de fois que le rang est divisible par 2 : les rangs 2, 6, 10, … donnent le plus petit triangle, les rangs 4, 12, 20 le suivant, etc. Cette régularité provient du fait que chaque diagonale parallèle au bord droit possède une période qui est une puissance de 2 ; lorsqu’un rang est multiple de cette période, la diagonale reste blanche.

Ces ordres périphériques n’atteignent pas la colonne centrale. À la rangée t, la colonne centrale se trouve sur la t‑ième diagonale depuis chaque bord ; les périodes de ces diagonales croissent rapidement (par exemple, la 54ᵉ diagonale se répète seulement après 4 194 304 rangs). Ainsi, aucune preuve d’ordre n’est encore disponible pour le centre, ce qui rend le problème de répétition de la colonne centrale particulièrement difficile.

Un résultat partiel montre que si la colonne centrale était périodique (par exemple, blanc‑noir‑blanc‑noir indéfiniment), la colonne adjacente entrerait dans une boucle de 56 étapes, décrite comme une « roue » combinant deux cycles de 8 et 7 positions. De plus, connaître la colonne centrale et son voisin immédiat force de façon unique toutes les cellules situées à gauche, ce qui implique que toute configuration finie avec un nombre limité de cellules noires finirait par devenir entièrement blanche au-delà d’une certaine profondeur.