thumb|250px|right| À gauche, une règle locale simple : une cellule passe d'un état (i) au suivant (i+1) dans le cycle d'états dès que i+1 est présent dans au moins 3 des 8 cellules voisines. À droite, le résultat (complexe) de l'application répétée de cette règle sur une grille de cellules. Ce type d'automates cellulaires a été découvert par D. Griffeath. Un automate cellulaire consiste en un ensemble d'automates, appelés « cellules », disposées sur une grille régulière et contenant chacune un « état » choisi parmi un ensemble fini. L'état d'une cellule évolue par pas de temps discrets, à l'aide d'une règle locale, laquelle prend en compte l'état d'un nombre fini de cellules appelé « voisinage » de la cellule. Classiquement, à chaque pas de temps, la même règle est appliquée simultanément à toutes les cellules de la grille, produisant une nouvelle « génération » de cellules, ou configuration, à partir de la configuration précédente.
Étudiés en mathématiques et en informatique théorique, les automates cellulaires sont à la fois un modèle de système dynamique discret et un modèle de calcul. Le modèle des automates cellulaires est remarquable par l'écart entre la simplicité de sa définition et la complexité que peuvent atteindre certains comportements macroscopiques : l'évolution dans le temps de l'ensemble des cellules ne se réduit pas (simplement) à la règle locale qui définit le système. À ce titre il constitue un des modèles standards dans l'étude des systèmes complexes.
Exemples Les automates cellulaires les plus simples 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 : 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
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 à :
center|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écimal s’écrit 00011110 en binaire et 00011110 est la deuxième ligne du tableau ci-dessus, décrivant la règle d'évolution.
Règle 110
Motif initial (t) 111 110 101 100 011 010 001 000 Valeur suivante de la cellule centrale (t+1) 0 1 1 0 1 1 1 0
a prouvé que l'automate cellulaire élémentaire numéro 110 (01101110 en binaire) est Turing-complet. 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 de Stephen Wolfram. En effet, 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 Matthew Cook a finalement été publiée dans une revue scientifique en 2004M. Cook, Universality in Elementary Cellular Automata, Complex Systems, 15(1), 2004, pp. 1-40..
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 étatsN. Ollinger, G. Richard, A Particular Cellular Automaton.N. Ollinger et G. Richard, Four states are enough!, Theoretical Computer Science (2010), ..
Le jeu de la vie thumb|199px|right|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).
Tous les autres…
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 règles. Ceci donne :
2 états 3 états 4 états 5 états 2 voisins 16 19 683 4 294 967 296 3 voisins 256 7 625 597 484 987 4 voisins 65 536 5 voisins 4 294 967 296 6 voisins
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.
Histoire
Dans les années 1940, Stanislaw Ulam étudiait la croissance des cristaux au laboratoire national de Los Alamos, en la modélisant sur une grille. Dans le même temps, John von Neumann, collègue d'Ulam à Los Alamos, travaillait sur des systèmes auto-réplicatifs et rencontrait des difficultés pour expliciter son modèle initial d'un robot qui se copierait tout seul à partir d'un ensemble de pièces détachées. Ulam lui suggéra de s'inspirer de ses travaux, ce qui conduisit von Neumann à concevoir un modèle mathématique abstrait pour son problème. Le résultat fut le « copieur et constructeur universel » ( en anglais), le premier automate cellulaire : il était basé sur une grille à deux dimensions où chaque cellule pouvait prendre 29 états. Von Neumann y construisit un motif particulier et démontra qu'il pouvait produire sans fin des copies de lui-mêmeJohn von Neumann, Arthur W. Burks, Theory of Self-Reproducing Automata, University of Illinois Press (1966)..
En 1969, Gustav Arnold Hedlund publie Endomorphisms and Automorphisms of the Shift Dynamical System, une monographie de 60 pages environ qui synthétise 10 ans de recherche d'une communauté travaillant dans le domaine de la dynamique symbolique (une branche de l'étude des systèmes dynamiques en mathématiques, fondée notamment par M. Morse et G. A. HedlundM. Morse et G. A. Hedlund, Symbolic Dynamics (American journal of Mathematics, vol. 60, 1938).). C'est cette publication qui pose les bases mathématiques de l'étude des automates cellulaires comme des systèmes dynamiques particuliers.
En 1969 également, Konrad Zuse publia Rechnender Raum (« Quand l'espace calcule »)Konrad Zuse, Rechnender Raum, Schriften zur Datenverarbeitung Band, Friedrich Vieweg & Sohn, Brunswick (1969). où il émettait l'hypothèse que les lois physiques étaient discrètes et que l'Univers était le résultat d'un gigantesque automate cellulaire.
Dans les années 1970, un automate cellulaire à deux dimensions et deux états nommé le « jeu de la vie », inventé par John Conway, connut un grand succès, particulièrement parmi la communauté informatique naissante. Il fut popularisé par Martin Gardner dans un article du Scientific AmericanMartin Gardner, Mathematical Games. The fantastic combinations of John Conway's new solitaire game « life », Scientific American n°223 (Octobre 1970), p. 120-123..
En 1983, Stephen Wolfram publia la première d'une série de publications où il analysait de façon systématique un type d'automates cellulaires très simplesStephen Wolfram, Universality and Complexity in Cellular Automata, Physica D (Janvier 1984), p. 1-35.. La complexité de leur comportement, induit par des règles élémentaires, le poussa à conjecturer que des mécanismes similaires pourraient expliciter des phénomènes physiques complexes, idées qu'il développa dans son livre A New Kind of Science paru en 2002Stephen Wolfram, A New Kind of Science, Wolfram Media (2002) - ..
Théorie des automates cellulaires
Si la popularité du modèle des automates cellulaires vient en grande partie d'une approche expérimentale, il fut dès l'origine abordé comme un objet mathématique par Von Neumann. La plupart des travaux formels sur les automates cellulaires utilisent la définition ci-dessous bien que le modèle admette de nombreuses généralisations et variations intéressantes.
Une définition formelle
Un automate cellulaire est un -uplet où : est la dimension de l'automate, son réseau est alors , l'espace discret de dimension ; , un ensemble fini, est son alphabet ; est son voisinage (un sous-ensemble fini du réseau) ; est sa règle locale de transition et 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 , c'est-à-dire une fonction de dans .
À cette description finie et locale, on associe la fonction globale d'évolution de l'automate, , qui agit sur les configurations et qui est définie par pour toute configuration (où ).
Systèmes dynamiques
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 et l'alphabet sont fixés, on peut munir l'espace des configurations de la métrique de Cantor par la distance définie par
L'ensemble des automates cellulaires d'alphabet et de dimension est alors caractérisé par le théorème de Curtis-Hedlund-LyondonG. A. Hedlund, Endomorphisms and Automorphisms of the Shift Dynamical System (Mathematical Systems Theory, vol. 3, n° 4, 1969). : est la fonction globale d'un tel automate cellulaire si et seulement si c'est une fonction continue de qui commute avec les fonctions de décalage (à toute position dans le réseau de cellules correspond une fonction de décalage ).
À 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.