Automate cellulaire

L'automate cellulaire non trivial le plus simple que l'on puisse concevoir consiste en une grille unidimensionnelle de cellules ne pouvant prendre que deux états (« 0 » ou « 1 »), avec un voisinage constitué, pour chaque cellule, d'elle-même et des deux cellules qui lui sont adjacentes.

Chacune des cellules pouvant prendre deux états, il existe 2³ = 8 configurations (ou motifs) possibles d'un tel voisinage. Pour que l'automate cellulaire fonctionne, il faut définir quel doit être l'état, à la génération suivante, d'une cellule pour chacun de ces motifs. Il y a 2⁸ = 256 façons différentes de s'y prendre, soit donc 256 automates cellulaires différents de ce type.

Les automates de cette famille sont dits « élémentaires ». On les désigne souvent par un entier entre 0 et 255 dont la représentation binaire est la suite des états pris par l'automate sur les motifs successifs 111, 110, 101, etc.

À titre d'exemple, considérons l’automate cellulaire défini par la table suivante, qui donne la règle d'évolution :

Cela signifie que si par exemple, à un temps t donné, une cellule est à l'état « 1 », sa voisine de gauche à l'état « 1 » et sa voisine de droite à l'état « 0 » (colonne 2 du tableau), au temps t+1 elle sera à l'état « 0 ».

Si l'on part d'une grille initiale où toutes les cellules sont à l'état « 0 » sauf une, on aboutit à :

Exemple d'automate cellulaire unidimensionnel

où chaque ligne est le résultat de la ligne précédente.

Par convention cette règle est nommée « règle 30 », car 30 en décimale s’écrit 00011110 en binaire et 00011110 est la deuxième ligne du tableau ci-dessus, décrivant la règle d'évolution.

Quelques étapes d'évolution du jeu de la vie à partir d'une configuration initiale choisie au hasard.

Le « jeu de la vie » est un automate cellulaire bidimensionnel où chaque cellule peut prendre deux valeurs (« 0 » ou « 1 », mais on parle plutôt de « vivante » ou « morte ») et où son état futur est déterminé par son état actuel et par le nombre de cellules vivantes parmi les huit qui l'entourent :

• Si la cellule est vivante et entourée par deux ou trois cellules vivantes, elle reste en vie à la génération suivante, sinon elle meurt.
• Si la cellule est morte et entourée par exactement trois cellules vivantes, elle naît à la génération suivante.

En apparence simples, ces règles font émerger une forte complexité.

On peut sur le même principe imaginer un grand nombre de règles en faisant varier les seuils de naissance ou de survie, ou en ajoutant des états supplémentaires, etc. Parmi ces variations, on peut citer :

• Day & Night
• HighLife
• Immigration
• QuadLife

Certains ne prennent en compte pour déterminer les changements d'état d'une cellule que les voisins immédiats de la case considérée, mais d'autres prennent également en compte l'état des cellules voisines dans un rayon de deux cases, voire plus. D'autres attribuent aussi un poids plus important à certaines cases du voisinages qu'à d'autres (WeightedLife).

Les règles possibles pour définir un automate cellulaire sont très nombreuses, même avec un petit nombre d'états et un petit voisinage. En effet si le nombre d'états est q et le nombre de voisins est v, il y a ${\displaystyle q^{(q^{v})}}$ règles. Ceci donne :

	2 états	3 états	4 états	5 états
2 voisins	16	19 683	4 294 967 296	${\displaystyle >10^{17}}$
3 voisins	256	7 625 597 484 987	${\displaystyle >10^{38}}$	${\displaystyle >10^{87}}$
4 voisins	65 536	${\displaystyle >10^{38}}$	${\displaystyle >10^{154}}$	${\displaystyle >10^{436}}$
5 voisins	4 294 967 296	${\displaystyle >10^{115}}$	${\displaystyle >10^{616}}$	${\displaystyle >10^{2184}}$
6 voisins	${\displaystyle >10^{19}}$	${\displaystyle >10^{347}}$	${\displaystyle >10^{2466}}$	${\displaystyle >10^{10921}}$

Le modèle des automates cellulaire offre donc un terrain d'exploration immense. Il n'est pas difficile de programmer un simulateur d'automates cellulaires et la Toile regorge de réalisations plus ou moins abouties. Le site de Mirek Wojtowicz propose par exemple un logiciel de simulation et une galerie d'exemples très riche : Mirek's Cellebration. Un autre exemple de simulateur intéressant est Golly. Il est dédié principalement au jeu de la vie et optimisé pour cet automate en utilisant notamment des quadtree combinés avec du hachage.

Un automate cellulaire est un ${\displaystyle 4}$-uplet ${\displaystyle (d,Q,V,\delta )}$ où :

• ${\displaystyle d}$ est la dimension de l'automate, son réseau est alors ${\displaystyle \mathbb {Z} ^{d}}$, l'espace discret de dimension ${\displaystyle d}$ ;
• ${\displaystyle Q}$, un ensemble fini, est son alphabet ;
• ${\displaystyle V\subseteq \mathbb {Z} ^{d}}$ est son voisinage (un sous-ensemble fini du réseau) ;
• ${\displaystyle \delta :Q^{a}\rightarrow Q}$ est sa règle locale de transition et ${\displaystyle a=|V|}$ est l'arité de l'automate.

On appelle alors configuration l'attribution d'un état à chaque cellule du réseau : une configuration est un élément de ${\displaystyle Q^{\mathbb {Z} ^{d}}}$, c'est-à-dire une fonction de ${\displaystyle \mathbb {Z} ^{d}}$ dans ${\displaystyle Q}$.

À cette description finie et locale, on associe la fonction globale d'évolution de l'automate, ${\displaystyle F_{\delta }:Q^{\mathbb {Z} ^{d}}\rightarrow Q^{\mathbb {Z} ^{d}}}$, qui agit sur les configurations et qui est définie par ${\displaystyle F_{\delta }(c)=z\mapsto \delta {\bigl (}c(z+v_{1}),\ldots ,c(z+v_{a}){\bigr )}}$ pour toute configuration ${\displaystyle c\in Q^{\mathbb {Z} ^{d}}}$ (où ${\displaystyle V=\{v_{1},\ldots ,v_{a}\}}$).

Les automates cellulaires ont été étudiés comme des systèmes dynamiques dès les années 1960 avec les travaux de G. A. Hedlund. Lorsque la dimension ${\displaystyle d}$ et l'alphabet ${\displaystyle Q}$ sont fixés, on peut munir l'espace des configurations de la métrique de Cantor par la distance ${\displaystyle d_{C}}$ définie par ${\displaystyle d_{C}(c,c')=2^{-\min\{|z|:c(z)\not =c'(z)\}}.}$

L'ensemble des automates cellulaires d'alphabet ${\displaystyle Q}$ et de dimension ${\displaystyle d}$ est alors caractérisé par le théorème de Curtis-Hedlund-Lyondon[7] : ${\displaystyle F}$ est la fonction globale d'un tel automate cellulaire si et seulement si c'est une fonction continue de ${\displaystyle {\bigl (}Q^{Z^{d}},d_{C}{\bigr )}}$ qui commute avec les fonctions de décalage (à toute position ${\displaystyle z}$ dans le réseau de cellules correspond une fonction de décalage ${\displaystyle \sigma _{z}(c)=z'\mapsto c(z+z')}$).

À partir de là, les automates cellulaires peuvent être étudiés avec tout l'outillage de la théorie des systèmes dynamiques classique, de la théorie du chaos et de la théorie ergodique, lorsque l'on munit l'espace des configurations d'une mesure.

Cette branche de la théorie des automates cellulaires reste largement ouverte et fait toujours l'objet de recherches (voir ici pour un exemple de question importante non résolue à ce jour).

• l'algorithme de P. C. Fischer pour reconnaître les nombres premiers
• le problème de la ligne de fusiliers : une solution ayant 6 états seulement a été publiée par Jacques Mazoyer, il a également prouvé qu'il n'y avait pas de solution à 4 états.

On peut considérer les automates cellulaires aussi bien comme des systèmes dynamiques discrets que comme des systèmes de calcul. Ainsi, chaque automate est capable de réaliser certains calculs ou d'exhiber certains comportements dynamiques. Que l'on adopte l'un ou l'autre des points de vue, on peut se poser une même question : existe-t-il un automate capable de faire tout ce que peuvent faire les automates cellulaires ? Un tel automate est alors dit universel.

La notion d'universalité correspond à une idée très simple et très générale, mais il faut prendre garde au fait que selon le sens que l'on met derrière l'expression « capable de faire » les automates universels ne sont pas les mêmes. On peut distinguer deux types de notions d'universalité pour les automates cellulaires : l'universalité Turing qui est associée à la capacité de calcul et l'universalité intrinsèque qui est associée à la capacité de produire certains comportements dynamiques.

Le fait remarquable est que pour chacune de ces notions il existe des automates universels. Il faut noter également que la notion d'universalité intrinsèque est plus forte que l'universalité Turing : en effet, sans rentrer dans les détails, un automate capable de simuler tous les automates peut en particulier simuler un automate Turing-universel et donc effectuer tous les calculs Turing. En revanche, il existe des automates cellulaires Turing-universels qui ne sont pas intrinsèquement universels.

L'universalité Turing est une adaptation aux automates cellulaires de l'universalité pour le calcul. On peut définir cette notion comme la capacité d'un automate à simuler une machine de Turing universelle. Cette possibilité de simulation d'une machine de Turing par un automate cellulaire est très simple et était connue dès les travaux de John von Neumann. Il existe plusieurs manières de la formaliser et ce qui suit est l'une des plus simples. Si ${\displaystyle M}$ est une machine de Turing fonctionnant avec un alphabet de ruban ${\displaystyle \Sigma }$ et un ensemble d'état ${\displaystyle Q}$, on peut définir un automate cellulaire ${\displaystyle A}$ capable de simuler ${\displaystyle M}$ :

• l'alphabet de ${\displaystyle A}$ est ${\displaystyle \Sigma \times {\bigl (}Q\cup \{\bot \}{\bigr )}}$ : ainsi chaque cellule de ${\displaystyle A}$ possède un état ${\displaystyle (\sigma ,q)}$ formé d'une composante ${\displaystyle \sigma }$ qui correspond au contenu du ruban et d'une composante ${\displaystyle q}$ qui correspond à l'absence (${\displaystyle q=\bot }$) ou la présence (${\displaystyle q\in Q}$) d'une tête de Turing à cette position et qui donne le cas échéant son état ;
• son voisinage est ${\displaystyle \{-1,0,1\}}$
• le comportement de ${\displaystyle A}$ consiste à reproduire les mouvements de la tête de Turing sur la première composante et les modifications du ruban sur la deuxième composante exactement comme le ferait ${\displaystyle M}$ :

un automate cellulaire simulant un système de calcul Turing

On rencontre souvent une acception plus générale (mais plus informelle) de l'universalité Turing : un automate cellulaire est Turing-universel s'il est capable de simuler un système de calcul Turing-complet. Le terme simuler est rarement formalisé dans un cadre général. Le point important est que la transformation des entrées/sorties du système simulé vers des entrées/sorties du simulateur reste simple : sans cette condition, on obtient une notion dénuée d'intérêt car des automates qui ne font rien (l'identité par exemple) deviennent universels grâce à des transformations d'entrées/sorties qui font tout le calcul à leur place.

Un automate cellulaire intrinsèquement universel est un automate capable de simuler pas à pas le comportement de n'importe quel automate cellulaire de même dimension. Plus précisément, l'idée de simulation pas à pas repose sur les principes suivants :

• dans l'automate simulateur, on forme des groupes de cellules voisines, tous identiques, qui recouvrent régulièrement le réseau de cellules ; chaque groupe dans le simulateur représente une cellule simple de l'automate simulé ;
• à chaque état de l'automate simulé correspond une configuration d'états de groupe dans l'automate simulateur ;
• l'automate simulateur peut utiliser plusieurs étapes pour simuler une étape de l'automate simulé.

Ainsi, par exemple, le jeu de la vie est capable de simuler pas à pas l'automate ${\displaystyle B}$ à 2 états (noir et rouge) qui effectue un simple décalage des états vers le sud-est :

• les groupes de cellules dans le jeu de la vie sont des carrés de ${\displaystyle 4\times 4}$ cellules ;
• l'état noir de ${\displaystyle B}$ correspond à un groupe de cellules toutes mortes et l'état rouge correspond à un planeur entouré de cellules mortes et ajusté dans une certaine position au sein du groupe ;
• une étape de ${\displaystyle B}$ est simulée toutes les 16 étapes du jeu de la vie.

Ainsi, pour simuler le comportement de ${\displaystyle B}$ à partir d'une certaine configuration initiale, il suffit de fabriquer une configuration du jeu de la vie où chaque groupe est soit rempli de cellules mortes, soit d'un planeur selon l'état de la cellule qui lui correspond dans ${\displaystyle B}$.

simulation automate cellulaire

Il est remarquable qu'avec ce principe de simulation très simple certains automates soient capables de simuler n'importe quel automate cellulaire à partir de n'importe quelle configuration : c'est le cas du jeu de la vie comme expliqué dans la section suivante. Bien entendu, pour simuler des automates avec de plus en plus d'états, un automate intrinsèquement universel utilise des groupes de cellules de plus en plus grands. En effet, avec un type de groupe de cellules fixés, il n'existe qu'un nombre fini de simulations possibles. Ainsi, quand on observe une évolution du jeu de la vie sur un écran (aussi grand soit il), on ne voit pas tous les comportements que le jeu de la vie est capable de simuler ; pourtant cet automate est capable de produire tous les comportements d'automate cellulaire.

Un exemple d'évolution de l'automate cellulaire élémentaire 110 utilisé dans la preuve d'universalité de M. Cook (le temps progresse de haut en bas).

Historiquement, le premier automate cellulaire construit ayant une propriété d'universalité (Turing en l'occurrence) est le constructeur universel de John von Neumann : il s'agit d'un automate de dimension 2 à 29 états qui est en outre capable de s'auto-répliquer.

Concernant la notion d'universalité intrinsèque, il faut attendre les années 1970 avec les travaux de E. R. Banks[8] qui proposa un automate cellulaire de dimension 2 à 2 états et 5 voisins. Il propose également un automate de dimension 1 intrinsèquement universel avec 5 états mais dont le voisinage est énorme.

L'exemple le plus célèbre d'automate universel est certainement le jeu de la vie. Il fut prouvé Turing-universel dans l'ouvrage Winning Ways for your Mathematical Plays. La preuve consiste à construire des morceaux de configurations qui peuvent être assemblés et qui correspondent à tous les composants nécessaires à la fabrication de circuits logiques (fils, croisements de fils, duplication, portes logiques, etc.). On peut trouver une construction complète d'une machine de Turing dans le jeu de la vie sur le site de Paul Rendell. À partir des mêmes idées, le jeu de la vie fut plus récemment prouvé intrinsèquement universel[9].

Pour la dimension 1, une percée concernant l'universalité Turing a eu lieu récemment : M. Cook a prouvé que l'automate cellulaire élémentaire numéro 110 était Turing-universel. Il a présenté ses idées dès 1998 à la conférence CA98, mais ce résultat n'a été (partiellement) diffusé par écrit qu'en 2002 à travers A New Kind of Science[6] de S. Wolfram. En effet, M. Cook était employé par Wolfram Research pour travailler sur le livre A New Kind of Science et ses travaux ne furent pas publiés dans les actes de CA98 à la suite d'une action en justice fondée sur un accord de non-divulgation. La preuve complète du résultat de M. Cook a finalement été publiée dans une revue scientifique en 2004[10].

En revanche, on ne sait toujours pas aujourd'hui si l'automate 110 est intrinsèquement universel ou pas. Le plus petit automate de dimension 1 avec un voisinage de 3 cellules qui ait été prouvé intrinsèquement universel à ce jour comporte 4 états[11]^,[12].

De façon générale, il est extrêmement difficile de déterminer le comportement global d'un automate cellulaire en examinant sa règle locale de transition. Ceci se traduit par des résultats d'indécidabilité touchant les propriétés les plus simples. Dans ce domaine on peut citer les travaux de Jarkko Kari qui, en utilisant de façon astucieuse les résultats déjà connus sur les pavages, a montré que les problèmes suivants étaient indécidables :

• savoir si un automate cellulaire est nilpotent (i.e. toutes les configurations mènent au bout d'un temps fini vers une même configuration uniforme)[13],
• savoir si un automate cellulaire de dimension ${\displaystyle d\geq 2}$ peut atteindre toutes les configurations après une étape (problème de la surjectivité)[14],
• savoir si un automate cellulaire de dimension ${\displaystyle d\geq 2}$ est réversible[14].

Le fait que des automates cellulaires puissent simuler n'importe quelle machine de Turing amène aussi des problèmes indécidables d'une autre nature. Par exemple, pour certains automates cellulaires, les problèmes suivants sont également indécidables :

• savoir si, étant donné un motif ${\displaystyle m}$ présent initialement au centre, un motif ${\displaystyle m'}$ va apparaître au centre au bout d'un certain temps,
• savoir si un motif ${\displaystyle m}$ peut apparaître arbitrairement tard dans l'évolution ou, au contraire, s'il existe un temps au-delà duquel ${\displaystyle m}$ n'apparaît plus quelle que soit la configuration de départ.

Un automate cellulaire ${\displaystyle A}$ est réversible s'il existe un automate cellulaire ${\displaystyle B}$ tel que les deux fonctions globales d'évolution ${\displaystyle F_{A}}$ et ${\displaystyle F_{B}}$ sont inverses l'une de l'autre : ${\displaystyle F_{B}\circ F_{A}}$ est la fonction identité. Intuitivement, ${\displaystyle B}$ « remonte le temps » de l'évolution de ${\displaystyle A}$ et, inversement, ${\displaystyle A}$ « remonte le temps » de l'évolution de ${\displaystyle B}$. Par le théorème de Hedlund, on peut caractériser les automates cellulaires réversibles comme ceux dont la fonction globale est bijective.

Cette classe a été très étudiée, notamment car elle fournit un modèle qui se rapproche du monde physique réel, supposé réversible à l'échelle microscopique (voir à ce sujet l'article sur la réversibilité et l'irréversibilité en thermodynamique). T. Toffoli et N. Margolus[15] sont parmi les premiers à s'être intéressés spécifiquement aux automates cellulaires réversibles. L'intérêt réside aussi dans la recherche de systèmes de calcul réversibles supposés consommer moins d'énergie d'après le principe de Landauer. Il est aujourd'hui établi que certains automates cellulaires réversibles sont Turing universels (travaux de Kenichi Morita).

Il est algorithmiquement impossible de distinguer les automates cellulaires réversibles de ceux qui ne le sont pas lorsque la dimension est supérieure à 2. En revanche, en dimension 1, il existe un algorithme très efficace.

Une autre façon de présenter cette différence entre la dimension 1 et les dimensions supérieures est la suivante : la taille du voisinage de l'inverse d'un automate ${\displaystyle A}$ ne peut pas être borné récursivement en fonction de la taille du voisinage de ${\displaystyle A}$ lorsque la dimension est 2 ou plus, alors qu'elle est bornée polynomialement en dimension 1 (un résultat récent[16] montre même que la borne est linéaire).

Technique du « second ordre » appliquée à l'automate cellulaire élémentaire 54 (le temps progresse de bas en haut).

Il est facile de construire des automates cellulaires réversibles. Pour cela, plusieurs formes de constructions existent.

1. la technique dite « du second ordre » : elle consiste à mélanger par une opération de OU exclusif bit à bit les informations du nouvel état d'une cellule avec son état passé. A priori, un automate cellulaire calcule la génération ${\displaystyle t+1}$ en fonction de la génération ${\displaystyle t}$ uniquement : la technique du second ordre paraît donc être une entorse au modèle. On peut contourner ce problème en fusionnant deux générations en une seule grâce à l'utilisation de plus d'états.
2. la technique des permutations par blocs alternées : elle a été proposée dans une version simple par Norman Margolus. Elle consiste à découper le réseau de cellules en blocs de cellules, à appliquer une permutation des états des cellules dans chaque bloc indépendamment, puis à décaler ce partitionnement et à appliquer une nouvelle permutation.
3. la technique du partitionnement : elle a été proposée par K. Morita et M. Harao[17]. Elle consiste à appliquer une transformation purement locale sur chaque cellule, puis, en utilisant un partitionnement de l'ensemble d'états, à envoyer à chaque cellule voisine une certaine composante de cet état. Avec cette construction, on a la garantie que l'automate cellulaire est réversible si la transformation locale appliquée est elle-même réversible.

Les automates cellulaires sont en général des systèmes dynamiques non linéaires, ce qui rend leur étude par des outils classiques difficile. Mais cette vérité générale n'empêche pas certains automates cellulaires de posséder une forme plus ou moins stricte de linéarité.

Quelques étapes d'évolution sur une configuration périodique d'un automate cellulaire additif à 5 états, en dimension 2, et avec tous les ${\displaystyle a_{i}}$ égaux à 1.

Formellement, un automate d'alphabet ${\displaystyle Q}$ est dit linéaire si l'on peut munir ${\displaystyle Q}$ d'une loi de groupe ${\displaystyle \oplus }$ telle que :

• ${\displaystyle \delta (x_{1}\oplus y_{1},x_{2}\oplus y_{2},\ldots )=\delta (x_{1},x_{2},\ldots )\oplus \delta (y_{1},y_{2},\ldots )}$

Dans ce cas, si l'on étend ${\displaystyle \oplus }$ à une opération agissant cellule à cellule sur l'espace des configurations, la fonction globale ${\displaystyle F_{\delta }}$ associée à l'automate est bien une fonction linéaire.

La linéarité facilite considérablement l'étude de la dynamique des automates. Ainsi, il suffit de connaître la dynamique d'un automate linéaire sur une « base » de l'espace de ses configurations pour en déduire par linéarité son comportement sur tout l'espace. On peut choisir pour une telle base l'ensemble (fini) des configurations partout égales à ${\displaystyle e}$ (neutre de ${\displaystyle \oplus }$) sauf éventuellement en la cellule centrale.

L'une des familles les plus étudiées d'automates linéaires est celle des automates dits additifs, introduite par O. Martin, A. Odlyzko et S. Wolfram dans[18]. Ces automates sont définis de la façon suivante :

• ${\displaystyle Q=\{0,\ldots ,n-1\}}$,
• ${\displaystyle \delta (x_{1},x_{2},\ldots )=\sum _{i}a_{i}x_{i}{\pmod {n}}}$ où les coefficients ${\displaystyle a_{i}}$ sont fixés et caractérisent l'automate.

L'exemple typique est celui où tous les coefficients ${\displaystyle a_{i}}$ sont égaux à 1 : la règle locale consiste alors à faire la somme modulo n de toutes les cellules du voisinage. Ainsi, en dimension 1, l'automate cellulaire élémentaire 90 est additif : sa fonction de transition consiste à faire la somme modulo 2 des états des deux voisines de la cellule. Il suffit de connaître le comportement de cet automate sur la configuration ${\displaystyle c_{0}}$ partout égale à 0 sauf au centre où elle vaut 1 pour en déduire son comportement général par le principe de superposition :

principe de superposition dans un automate cellulaire

L'automate élémentaire 102 est également additif. Son action sur la configuration ${\displaystyle c_{0}}$ produit un triangle de Pascal modulo 2 (qui donne aussi une approximation du triangle de Sierpinski). Ainsi, partant de ${\displaystyle c_{0}}$, la cellule ${\displaystyle z}$ après ${\displaystyle t}$ étapes se trouve dans l'état :

• ${\displaystyle 0}$ si ${\displaystyle z>0}$ ou ${\displaystyle z<-t}$,
• ${\displaystyle {t \choose |z|}{\pmod {2}}}$ dans les autres cas.

Par superposition, on en déduit une expression directe de l'état de la cellule centrale après ${\displaystyle t}$ étape partant d'une configuration quelconque ${\displaystyle c}$ :

• ${\displaystyle \sum _{i=0}^{t}c(i){{t} \choose {t-i}}{\pmod {2}}}$.

Dans un automate cellulaire totalistique, l'état ultérieur d'une cellule ne dépend que de la somme des états de ses voisines ; c'est le cas du jeu de la vie où une cellule vivante le reste si deux ou trois de ses voisines sont vivantes, et une cellule morte naît si trois de ses voisines sont vivantes. Un automate totalistique ne prend donc pas en compte la position des voisines d'une cellule par rapport à celle-ci.

Automate sommatif (totalistique) tridimensionnel défini sur un réseau dodécaédrique rhombique

Si un automate cellulaire n'est pas totalistique, en plus de leur état propre, la position des voisines d'une cellule influe sur son état ultérieur. Par exemple, pour un automate cellulaire à une dimension, on peut faire une différence entre la cellule voisine de gauche et la voisine de droite.

Cette classification fut introduite par Stephen Wolfram en 1983 dans son article Universality and complexity in cellular automata et représente la première tentative pour classifier les automates cellulaires d'après leur évolution à partir de configurations initiales aléatoires. Il proposa quatre classes de comportement :

• Classe I : presque toute configuration initiale conduit à un état homogène. Il est impossible de construire des motifs stables périodiques.
• Classe II : des structures stables ou périodiques émergent, mais rien de plus.
• Classe III : comportement chaotique avec des motifs apériodiques. À long terme les fréquences d'apparitions des différents motifs se stabilisent.
• Classe IV : « émergence » de structures complexes capables d'osciller, de se mouvoir, voire de persévérer plus ou moins dans leur auto-organisation malgré des perturbations structurelles. Le jeu de la Vie en est un parfait exemple.

Une des critiques de la classification de Wolfram réside dans son impossibilité à dire si un automate cellulaire donné est Turing-universel ; d'ailleurs, des automates cellulaires universels ont été trouvés pour chacune des classes proposées par Wolfram. Cet état de fait provient de ce que Wolfram n'a considéré que des conditions initiales aléatoires, mais pas des structures particulières créées spécifiquement pour l'occasion. En particulier, la transmission d'information, par exemple par l'intermédiaire de vaisseaux, n'est pas prise en compte.

David Eppstein a proposé une alternative à cette classification :

• Expansion obligatoire des motifs : n'importe quel motif initial s'étend indéfiniment dans toutes les directions. Aucun vaisseau ne peut exister.
• Expansion impossible : un motif ne peut jamais s'étendre au-delà de ses limites initiales. Aucun vaisseau ne peut exister.
• Contraction impossible : un motif ne s'étend pas forcément indéfiniment, mais il ne peut jamais réduire en deçà de ses limites initiales. Aucun vaisseau ne peut exister.
• Expansion et contraction possibles : seuls ces cas peuvent contenir des vaisseaux.

A priori, seuls les derniers cas permettent l'universalité, même si tous les automates cellulaires qui y répondent ne le sont pas. En revanche, il n'a pas été non plus démontré qu'il est impossible de construire des structures universelles pour les autres cas, d'autres structures que les vaisseaux pouvant également transmettre des informations.

Dans la définition formelle ci-dessus, le réseau est systématiquement de la forme ${\displaystyle Z^{d}}$. On peut généraliser sans problème à d'autres graphes infinis réguliers.

La première classification d'un automate cellulaire concerne la façon dont les règles sont appliquées sur la grille :

• Pour les automates cellulaires à traitement parallèle, l'état de toutes les cellules est mis à jour à chaque tour.
• Pour les automates cellulaires à traitement série, seul l'état d'une ou plusieurs cellules est mis à jour.

Il est possible de généraliser le concept d'automate cellulaire, par exemple :

• en modifiant le voisinage au cours du temps

Les automates continus fonctionnent sur le même principe que les automates cellulaires, mais utilisent des grilles ou des états continus (le plus souvent entre 0 et 1). De tels automates peuvent simuler par exemple la diffusion d'un liquide.

Un automate cellulaire probabiliste est un automate cellulaire déterministe où la règle locale f est remplacée par une dynamique locale aléatoire, c'est-à-dire une matrice de transition qui indique en fonction de l'état où l'on est avec quelle probabilité on peut se retrouver dans un état suivant.

Il est possible de répéter un automate cellulaire sur l'image trouvée à la suite d'une application du même automate cellulaire probabiliste. On peut itérer cela une infinité de fois. La recherche de loi invariante où de l'ergodicité (convergence) de la loi de départ sont des sujets sur lesquels des recherches sont faites actuellement.

Il est conjecturé (mais pas prouvé) que les automates cellulaires probabilistes sont tous ergodiques si le cardinal de l'alphabet de départ est égale à 2 et il est prouvé que cela est faux pour tous alphabet de très grande taille. Cela a été démontré par Gàcs en 2001 pour les automates cellulaires probabilistes avec un alphabet de cardinal de taille environ ${\displaystyle 2^{100}}$[19].

La question reste ouverte et n'est pas conjecturée pour les automates cellulaires probabilistes avec un alphabet de cardinal de taille plus petite.

Dans la recherche mathématique, les automates cellulaires probabilistes sont utilisés aussi pour conjecturer certaines lois sur les percolations de dernier passage généralisées.

Automate cellulaire appliqué aux feux de forêts : en rouge, les arbres qui brûlent, en vert les arbres intacts et en gris, les cendres. Ce programme utilise le voisinage de von Neumann (les arbres qui se situent à côté d'un arbre en feu brûlent à leur tour).

Parmi les modèles qui ont été très étudiés[21], on peut citer les automates de gaz sur réseau (lattice gaz automata en anglais) qui modélisent des particules de gaz régies par une version discrète des équations de Navier Stokes.

La première formulation de ce modèle, connu sous le nom de HPP, (il s'agit d'un automate cellulaire de dimension ${\displaystyle 2}$) est due à J. Hardy, Y. Pomeau et O. Pazzis dans les années 1970. Une seconde formulation, FHP, a été proposée dans les années 1980 par U. Frisch, B. Hasslacher et Y. Pomeau : elle améliore la précédente en remplaçant le réseau de cellule ${\displaystyle Z^{2}}$ par un réseau hexagonal.

Les automates cellulaires trouvent aussi une application dans la modélisation et la simulation des feux de forêts[22]. La première utilisation est due à Kourtz et O'Regan[23] en 1971. Ces modèles permettent facilement d'observer la propagation du feu en fonction de plusieurs paramètres comme la direction et la force du vent ou encore l'humidité.

Les motifs de certains coquillages, comme les cônes et les cymbiolae, sont générés par des mécanismes s'apparentant au modèle des automates cellulaires. Les cellules responsables de la pigmentation sont situées sur une bande étroite le long de la bouche du coquillage. Chaque cellule sécrète des pigments selon la sécrétion (ou l'absence de sécrétion) de ses voisines et l'ensemble des cellules produit le motif de la coquille au fur et à mesure de sa croissance. Par exemple, l'espèce Conus textile présente un motif ressemblant à la règle 30 décrite plus haut.

Conus textile présentant sur sa coquille un motif similaire à certains automates cellulaires

Automate cellulaire élémentaire 184 : en noir les portions d'autoroute vides, en bleu celles où une voiture est présente. Les zones qui semblent être d'un bleu plus foncé sont en fait formées d'une alternance de noir et de bleu et correspondent à une circulation fluide de densité maximale.

K. Nagel et M. Schreckenberg ont proposé dans les années 1990 un modèle de trafic autoroutier basé sur un automate cellulaire de dimension 1 :

• les cellules de l'automate représentent différentes portions de l'autoroute ;
• une cellule est soit dans l'état vide, soit dans l'un des états ${\displaystyle \{v_{1},\ldots ,v_{n}\}}$, où ${\displaystyle v_{i}}$ représentent la présence d'un véhicule roulant à la vitesse ${\displaystyle v_{i}}$ (${\displaystyle v_{1}}$ représente l'arrêt) ;
• le fonctionnement est schématiquement le suivant :

1. chaque véhicule accélère d'un cran (passe de ${\displaystyle v_{i}}$ à ${\displaystyle v_{i+1}}$) en limitant sa vitesse afin de ne pas parcourir en 1 unité de temps plus que la distance qui le sépare du véhicule devant lui,
2. la vitesse obtenue est diminuée d'un cran (passage de ${\displaystyle v_{j}}$ à ${\displaystyle v_{j-1}}$) avec une certaine probabilité ${\displaystyle p}$,
3. chaque véhicule avance d'une distance proportionnelle à sa vitesse ainsi déterminée.

Ce modèle correspond à un automate cellulaire si la perturbation aléatoire est absente (${\displaystyle p=0}$). Si de plus ${\displaystyle n=2}$ (un véhicule est soit à l'arrêt, soit à sa vitesse maximum), le modèle se réduit à l'automate cellulaire élémentaire 184 : les cellules peuvent prendre uniquement deux valeurs correspondant à vide ou présence d'un véhicule.

• Projet:Automate cellulaire
• Stephen Wolfram
• Théorème de Liouville (système dynamique)

• Systèmes dynamiques
• Théorie du chaos
• Informatique théorique
• Systèmes complexes
• Émergence
• Calcul parallèle

• Boids
• Automate cellulaire de Codd
• Boucle de Langton
• Constructeur universel
• Day & Night
• Fourmi de Langton
• HighLife
• Immigration (automate cellulaire)
• Jeu de la vie
• QuadLife
• vie sans mort
• Vers de Paterson
• Wireworld

• Nazim Fatès - Mémoire de DEA en histoire et philosophie des sciences sur les automates cellulaires.
• une bonne page d'entrée pour le jeu de la vie
• (en) Golly, un programme de simulation du jeu de la vie
• (en) Mirek's celebration, un automate cellulaire général

• John von Neumann, Arthur W. Burks, Theory of Self-Reproducing Automata, University of Illinois Press (1966)
• Konrad Zuse, Rechnender Raum, Schriften zur Datenverarbeitung Band, Friedrich Vieweg & Sohn, Braunschweig (1969)
• Martin Gardner, Mathematical Games. The fantastic combinations of John Conway's new solitaire game « life », Scientific American n^o 223 (octobre 1970), p. 120-123
• Stephen Wolfram, Universality and Complexity in Cellular Automata, Physica D n^o 10 (janvier 1984), p. 1-35
• Stephen Wolfram, A New Kind of Science, Wolfram Media (2002) - (ISBN 1-57955-008-8)
• G. A. Hedlund, Endomorphisms and Automorphisms of the Shift Dynamical System (Mathematical Systems Theory, vol. 3, n° 4, 1969)
• J. Kari, The Nilpotency Problem of One-dimensional Cellular Automata, SIAM Journal on Computing 21 (1992), pp. 571-586
• J. Kari, Reversibility and Surjectivity Problems of Cellular Automata, Journal of Computer and System Sciences 48, 1 (1994), pp. 149-182
• T. Toffoli et N. Margolus, Invertible Cellular Automata: a review, Physica D, 45 (1990), pp. 229–253
• E. Czeizler et J. Kari, A tight linear bound on the neighborhood of inverse cellular automata, ICALP 2005, Lecture Notes in computer Science 3580, pp. 410–420, Springer-Verlag
• O. Martin, A. Odlyzko et S. Wolfram, Algebraic Properties of Cellular Automata, Communications in Mathematical Physics (1984), n^o 93, p. 219
• M. Morse et G. A. Hedlund, Symbolic Dynamics (American journal of Mathematics, vol. 60, 1938)
• E. R. Banks, Universality in cellular automata, Eleventh Annual Symposium on Switching and Automata Theory (Santa Monica, California, 1970), IEEE
• B. Durand et Z. Róka, The game of life :universality revisited dans Cellular Automata : a Parallel Model, vol. 460 of Mathematics and its Applications. Kluwer Academic Publishers, 1999, pp. 51-74
• M. Cook, Universality in Elementary Cellular Automata, Complex Systems, 15(1), 2004, pp. 1–40.
• N. Ollinger, The quest for small universal cellular automata, International Colloquium on Automata, Languages and Programming (2002), Lecture Notes in Computer Science, pp. 318-330.