Automate cellulaire

À 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 une grille régulière de « cellules » contenant chacune un « état » choisi parmi un ensemble fini et qui peut évoluer au cours du temps. L'état d'une cellule au temps t+1 est fonction de l'état au temps t d'un nombre fini de cellules appelé son « voisinage ». À chaque nouvelle unité de temps, les mêmes règles sont appliquées simultanément à toutes les cellules de la grille, produisant une nouvelle « génération » de cellules dépendant entièrement de la génération 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 à :

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.

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

M. Cook^[Qui ?] 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^{[réf. nécessaire]}, mais ce résultat n'a été (partiellement) diffusé par écrit qu'en 2002 à travers A New Kind of Science^[1] 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^[2].

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^[3],[4].

Le jeu de la vie

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 ${\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.

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 » (universal copier and constructor 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ême^[5].

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. Hedlund^[6]). 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 »)^[7] 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 American^[8].

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 simples^[9]. 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 2002^[1].

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^[5]. 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 ${\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}\}}$).

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 ${\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^[10] : ${\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).

Modèle de calcul et constructions algorithmiques

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

Automates cellulaires universels

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.

Universalité Turing

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.

Universalité intrinsèque

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.

Exemples

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^[11] 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^[12].

Complexité

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.

Classes remarquables d'automates cellulaires

Comme expliqué plus haut, les règles locales d'automates cellulaires sont trop nombreuses pour une étude exhaustive et la prédiction du comportement en fonction de la règle local est un problème très difficile en général. C'est pourquoi l'étude des automates cellulaires s'est souvent restreinte à des familles particulières, soit parce qu'elles se prêtent plus facilement à l'analyse, soit parce qu'elles correspondent à une propriété intéressante.

Automates réversibles

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

Reconnaissance

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

Exemples

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.

Automates linéaires

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

Définition

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.

Automates additifs

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}}}$.

Automates totalistiques

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.

Automates conservatifs

Le problème des classifications

Classification de Wolfram

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.

Classification d'Eppstein

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.

Généralisation et variations sur le modèle

Réseau de cellules

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.

Asynchronisme

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.

Autres

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.

Automates cellulaires probabilistes

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.

Modélisation et applications

On peut considérer le modèle des automates cellulaires comme le pendant discret des équations aux dérivées partielles. Ainsi, à chaque fois qu'un phénomène physique est décrit par des équations aux dérivées partielles, on peut en proposer une (des) discrétisation(s) sous forme d'automate cellulaire^[20]. Il reste à déterminer dans quelle mesure le modèle cellulaire est pertinent pour expliquer et/ou prédire le phénomène étudié. Rien n'est garanti dans le cas général et caractériser la dynamique globale du modèle cellulaire en fonction de sa définition locale peut être au moins aussi difficile que de résoudre le système d'équations aux dérivées partielles.

En revanche, l'automate cellulaire peut être simulé facilement par ordinateur ! Ainsi, en analyse numérique, de nombreuses méthodes consistent à discrétiser certaines grandeurs (espace, temps, valeur) pour effectuer des simulations numériques (voir la méthode des éléments finis, des volumes finis ou des différences finies).

Modélisation en physique

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

Phénomènes biologiques

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

Trafic routier

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.

Les automates cellulaires comme des modèles physiques

Plusieurs scientifiques, tels qu'Andrew Ilachinski^[24], ont émis l'hypothèse selon laquelle l'univers pourrait être considéré comme un automate cellulaire^[24]. Ilachinski la justifie par l'observation suivante : « Considérons l'évolution de la règle 110 : s'il s'agissait d'une sorte de « loi alternative de la physique », quelle serait la description rationnelle des motifs observés ? Un observateur ignorant la règle appliquée pour générer les images pourrait supposer le mouvement d'objets discrets^[25]. » Le physicien James Crutchfield a émis une théorie mathématique rigoureuse basée sur ce principe, prouvant l'émergence statistique de « particules » dans les automates cellulaires^[26]. Par extension, l'univers, qui peut être décrit comme un ensemble de particules, pourrait ainsi être considéré comme un automate cellulaire.

En octobre 2014, une théorie unifiée basée sur cette hypothèse reste encore à être formulée ; néanmoins, les recherches en ce sens ont aidé certains chercheurs à définir l'univers comme un système discret :

• Marvin Minsky a étudié les interactions entre particules en se basant sur un automate cellulaire en quatre dimensions^[27] ;
• Konrad Zuse a développé une matrice irrégulière permettant l'étude des informations contenues par les particules^[28] ;
• Edward Fredkin a émis l'« hypothèse de la nature bornée », selon laquelle toute quantité physique, y compris l'espace et le temps, serait discrète et finie^[29] ;
• Stephen Wolfram, dans son livre A New Kind of Science, considère les automates cellulaires comme la clef permettant d'expliquer de nombreux sujets, dont la physique^[1] ;
• Gabriele Rossi, Francesco Berto et Jacopo Tagliabue, présentent dans Mathematics of the Models of Reference un univers, basé sur un « dodécaèdre rhombique » et une règle unique, satisfaisant à l'universalité, parfaitement réversible et permettant la formulation d'affirmations qualitatives quant à l'évolution de l'univers^[30].

Notes et références

1. Stephen Wolfram, A New Kind of Science, Wolfram Media (2002) - (ISBN 1-57955-008-8).
2. M. Cook, Universality in Elementary Cellular Automata, Complex Systems, 15(1), 2004, pp. 1-40.
3. N. Ollinger, G. Richard, A Particular Cellular Automaton.
4. N. Ollinger et G. Richard, Four states are enough!, Theoretical Computer Science (2010), DOI 10.1016/j.tcs.2010.08.018.
5. John von Neumann, Arthur W. Burks, Theory of Self-Reproducing Automata, University of Illinois Press (1966).
6. M. Morse et G. A. Hedlund, Symbolic Dynamics (American journal of Mathematics, vol. 60, 1938).
7. Konrad Zuse, Rechnender Raum, Schriften zur Datenverarbeitung Band, Friedrich Vieweg & Sohn, Brunswick (1969).
8. Martin Gardner, Mathematical Games. The fantastic combinations of John Conway's new solitaire game « life », Scientific American n°223 (Octobre 1970), p. 120-123.
9. Stephen Wolfram, Universality and Complexity in Cellular Automata, Physica D n^o 10 (Janvier 1984), p. 1-35.
10. G. A. Hedlund, Endomorphisms and Automorphisms of the Shift Dynamical System (Mathematical Systems Theory, vol. 3, n° 4, 1969).
11. E. R. Banks, Universality in cellular automata, Eleventh Annual Symposium on Switching and Automata Theory (Santa Monica, California, 1970), IEEE.
12. 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.
13. J. Kari, The Nilpotency Problem of One-dimensional Cellular Automata, SIAM Journal on Computing 21 (1992), pp. 571-586.
14. J. Kari, Reversibility and Surjectivity Problems of Cellular Automata, Journal of Computer and System Sciences 48, 1 (1994), pp. 149-182.
15. T. Toffoli et N. Margolus, Invertible Cellular Automata: a review, Physica D, 45 (1990), pp. 229-253.
16. 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.
17. K. Morita and M. Harao. Computation universality of 1 dimensional reversible (injective) cellular automata. Transactions Institute of Electronics, Information and Communication Engineers, E, 72:758762, 1989.
18. O. Martin, A. Odlyzko et S. Wolfram, Algebraic Properties of Cellular Automata, Communications in Mathematical Physics (1984), n°93, p. 219.
19. (en) Peter Gács, « Reliable Cellular Automata with Self-Organization », Journal of Statistical Physics, vol. 103, n^o 1,‎ 1^er avril 2001, p. 45–267 (ISSN 1572-9613, DOI 10.1023/A:1004823720305, lire en ligne, consulté le 26 décembre 2020)
20. P. Narbel, Qualitative and quantitative cellular automata from differential equations (Proceedings of ACRI 2006, LNCS vol. 4173, pp. 112-121, (ISBN 3-540-40929-7)).
21. B. Chopard et M. Droz Cellular automata modeling of physical systems (Cambridge University Press Collection Alea, 1998, (ISBN 978-0-521-67345-7)).
22. Jonathan MARGERIT, « Modélisation et Simulations Numériques de la Propagation de Feux de Forêts » [PDF], 7 novembre 2003
23. (en) Kourtz, A Model a Small Forest Fire . . . to Simulate Burned and Burning Areas for Use in a Detection Model, Society of American Foresters, 1971 (lire en ligne), pp 163-169
24. A. Ilachinsky, Cellular Automata, World Scientific Publishing, 2001, pp. 660.
25. A. Ilachinsky, Cellular Automata, World Scientific Publishing, 2001, pp. 661-662.
26. J. P. Crutchfield, The Calculi of Emergence: Computation, Dynamics, and Induction, Physica D 75, 11-54, 1994.
27. M. Minsky, Cellular Vacuum, Int. Jour. of Theo. Phy. 21, 537-551, 1982, DOI 10.1007/BF02650183.
28. K. Zuse, The Computing Universe, Int. Jour. of Theo. Phy. 21, 589-600, 1982, DOI 10.1007/BF02650187.
29. E. Fredkin, Digital mechanics: an informational process based on reversible universal cellular automata, Physica D 45, 254-270, 1990.
30. F. Berto, G. Rossi, J. Tagliabue, The Mathematics of the Models of Reference, College Publications, 2010.

Voir aussi

Sur les autres projets Wikimedia :

• Automate cellulaire, sur Wikibooks

Bibliographie

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

Articles connexes

• Projet:Automate cellulaire
• Stephen Wolfram
• Théorème de Liouville (système dynamique)
• Domaines apparentés : Théorie des systèmes dynamiques - Théorie du chaos - Informatique théorique - Système complexe - Émergence - Parallélisme
• Règles particulières : 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 (en) - Vers de Paterson - Wireworld

Liens externes

• Notices d'autorité :

  • BnF (données)
  • LCCN
  • GND
  • Israël
  • Tchéquie
• Notices dans des dictionnaires ou encyclopédies généralistes :

  • Britannica
  • Universalis
• Ressource relative à la recherche :
  • Stanford Encyclopedia of Philosophy
• Ressource relative à la santé :
  • Medical Subject Headings
• 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

• Portail de la logique
• Portail de l'informatique théorique