🔲 Automates Cellulaires 1D de Wolfram

Un système est Turing-complet s'il peut simuler tout calcul qu'un ordinateur généraliste peut effectuer, avec suffisamment de temps et de mémoire. Matthew Cook a prouvé en 2004 (avec l'autorisation de Wolfram de publier) que la règle 110 est Turing-complète en montrant qu'elle peut simuler un type spécifique de machine universelle appelée système de tag cyclique. Cela signifie que la règle 110 — une ligne unidimensionnelle de cellules binaires mise à jour par une table de seulement 8 bits — est en principe capable d'exécuter n'importe quel algorithme, ce qui en fait l'un des plus simples substrats de calcul universel connus.

La règle 184 correspond directement au processus d'exclusion simple asymétrique (ASEP), un modèle standard du flux de circulation. Chaque cellule vivante représente un véhicule, et la règle fait avancer les véhicules d'une position si la cellule devant est vide, sinon ils restent immobiles. Cela reproduit naturellement les phénomènes réels de circulation : à faible densité, les véhicules circulent librement à vitesse maximale ; au-delà d'une densité critique, un embouteillage se propage vers l'arrière comme une onde, même si des voitures isolées avancent occasionnellement. La règle 184 est utilisée en physique et en science des transports comme le modèle discret de circulation le plus simple capturant ce comportement d'onde de bouchon.

La règle 30 n'est pas aléatoire — elle est entièrement déterministe — mais le motif qu'elle génère à partir d'une seule cellule vivante est prouvé chaotique et réussit les tests statistiques standards de hasard. Wolfram a utilisé la colonne centrale de la règle 30 comme générateur de nombres pseudo-aléatoires dans Mathematica pendant de nombreuses années, et elle a été étudiée comme source de hasard cryptographique. Le motif est si sensible aux conditions initiales et si visuellement imprévisible que prédire les états futurs sans exécuter la règle pas à pas semble être calculatoirement irréductible : il n'existe aucun raccourci connu plus rapide que la simulation elle-même.

Les automates cellulaires unidimensionnels ont été étudiés pour la première fois au début des années 1980 par Stephen Wolfram, qui a réalisé une étude systématique assistée par ordinateur des 256 règles élémentaires et publié ses résultats dans une série d'articles à partir de 1983. Wolfram a classé les règles en quatre classes comportementales — points fixes, motifs périodiques, motifs chaotiques et comportement complexe (classe IV) — une taxonomie qui reste influente en science de la complexité aujourd'hui. Son livre ultérieur « A New Kind of Science » (2002) a étendu ces idées en une théorie grandiose proposant que des règles simples sont le fondement de toute la complexité naturelle.

Le Jeu de la Vie de Conway est l'automate cellulaire bidimensionnel le plus célèbre, utilisant un voisinage 3x3 au lieu d'une bande 1x3 ; il atteint aussi la Turing-complétude et produit des planeurs, des oscillateurs et des vaisseaux. La simulation du Triangle de Sierpiński sur ce site partage sa structure fractale avec la règle 90. Les systèmes de réaction-diffusion comme le modèle de Gray-Scott étendent l'idée de règles locales gouvernant la formation de motifs à la chimie continue. Les automates à voisinage plus large et totalistiques — où seul le compte de voisins vivants importe — incluent la famille contenant Brian's Brain et Wireworld, qui peuvent émuler des circuits logiques numériques.

Les automates cellulaires sous-tendent plusieurs technologies pratiques. La règle 30 et des automates apparentés ont été utilisés comme générateurs de nombres pseudo-aléatoires dans des systèmes de calcul formel. Les modèles à base d'automates cellulaires alimentent des simulations de dynamique des fluides via les méthodes de Lattice-Boltzmann, qui approximent les équations de Navier-Stokes sur une grille de règles de collision locales et sont utilisées dans la recherche en aérodynamique et microfluidique. En matériel, les registres à décalage à base d'automates cellulaires apparaissent dans les chiffrements de flux et les codes correcteurs d'erreurs. Des chercheurs ont aussi utilisé les automates cellulaires pour concevoir des systèmes robotiques auto-répliquants et de la matière programmable, inspirés de l'automate théorique auto-reproducteur de von Neumann des années 1950.

Les recherches actuelles explorent les automates cellulaires réversibles, où chaque configuration a un unique prédécesseur — pertinent pour l'informatique quantique et le calcul thermodynamiquement efficace. Il existe des travaux actifs sur les automates cellulaires continus (SmoothLife et Lenia), qui généralisent les règles discrètes à des états à valeurs réelles et produisent des organismes semblables au vivant qui se déplacent et se reproduisent. Les chercheurs étudient aussi les automates cellulaires comme modèles de l'espace-temps à l'échelle de Planck, se demandant si l'univers lui-même pourrait être un automate cellulaire. En apprentissage automatique, les réseaux de neurones convolutifs sont structurellement analogues aux automates cellulaires, et les automates cellulaires neuronaux ont été entraînés à faire croître des images cibles et à s'auto-réparer, ouvrant un nouveau domaine combinant apprentissage profond et paradigme des automates cellulaires.