Automate cellulaire

Un article de Wikipédia, l'encyclopédie libre.

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

É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. Un automate cellulaire consiste en une grille régulière de « cellules » pouvant chacune prendre à un instant donné un « état » parmi un ensemble fini. Le temps est également discret et 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.

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.

Sommaire

1 Histoire
2 Exemples
3 Théorie des automates cellulaires
4 Classes remarquables d'automates cellulaires
5 Le problème des classifications
- 5.1 Classification de Wolfram
- 5.2 Classification d'Eppstein
6 Généralisation et variations sur le modèle
7 Modélisation et Applications
8 Voir aussi
9 Notes et références

[modifier] 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^[1].

En 1969, G. A. 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^[2]). 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 (« Calculer l'espace »)^[3] 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^[4].

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^[5]. 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^[6].

[modifier] Exemples

[modifier] 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 dit "é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	111	110	101	100	011	010	001	000
Valeur suivante de la cellule centrale	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 », 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 à :

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 s'écrit 00011110 en binaire et 00011110 est la deuxième ligne du tableau ci-dessus, décrivant la règle d'évolution.

[modifier] 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 :

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

[modifier] Tous les autres...

Les règles possibles pour définir un automate cellulaires sont très nombreuses, même avec un petit nombre d'états et un petit voisinage :

	2 états	3 états	4 états	5 états
2 voisins	16	19 683	4 294 967 296	$> 10 17$
3 voisins	256	7 625 597 484 987	$> 10 38$	$> 10 87$
4 voisins	65 536	$> 10 38$	$> 10 154$	$> 10 436$
5 voisins	4 294 967 296	$> 10 115$	$> 10 616$	$> 10 2184$
6 voisins	$> 10 19$	$> 10 347$	$> 10 2466$	$> 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.

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

[modifier] Une définition formelle

Un automate cellulaire est un $4$ -uplet $(d, Q, V,δ)$ où :

$d$ est la dimension de l'automate, son réseau est alors $\mathbb{Z}^d$ , l'espace discret de dimension $d$ ;
$Q$ , un ensemble fini, est son alphabet ;
$V\subseteq \mathbb{Z}^d$ est son voisinage (un sous-ensemble fini du réseau) ;
$\delta : Q^a\rightarrow Q$ est sa règle locale de transition et $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 $Q^{\mathbb{Z}^d}$ , c'est à dire une fonction de $\mathbb{Z}^d$ dans $Q$ .

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

[modifier] 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 $d$ et l'alphabet $Q$ sont fixés, on peut munir l'espace des configurations de la métrique de Cantor par la distance $d C$ définie par $d_C(c,c') = 2^{-\min\{|z| : c(z)\not=c'(z)\}}.$

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

[modifier] Modèle de calcul et constructions algorithmiques

Cette section est vide, pas assez détaillée ou incomplète. Votre aide est la bienvenue !

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 éte publiée par Jacques Mazoyer, il a également prouvé qu'il n'y avait pas de solution à 4 états.

[modifier] 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 (plus ou moins intéressants) ou d'exhiber certains comportements dynamiques (plus ou moins complexes). 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.

[modifier] 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 $M$ est une machine de Turing fonctionnant avec un alphabet de ruban $Σ$ et un ensemble d'état $Q$ , on peut définir un automate cellulaire $A$ capable de simuler $M$ :

l'alphabet de $A$ est $\Sigma\times\bigl(Q\cup\{\bot\}\bigr)$ : ainsi chaque cellule de $A$ possède un état $(σ, q)$ formé d'une composante $σ$ qui correspond au contenu du ruban et d'une composante $q$ qui correspond à l'absence ( $q=\bot$ ) ou la présence ( $q\in Q$ ) d'une tête de Turing à cette position et qui donne le cas échéant sont état ;
son voisinage est ${ - 1,0,1}$
le comportement de $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 $M$ :

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.

[modifier] 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 $D$ à 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 $4\times 4$ cellules ;
l'état noir de $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 $B$ est simulée toutes les 16 étape du Jeu de la vie.

Ainsi, pour simuler le comportement de $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 planneur selon l'état de la cellule qui lui correspond dans $B$ .

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 comportement que le Jeu de la vie est capable de simuler ; pourtant cet automate est capable de produire tous les comportements d'automate cellulaire.

[modifier] 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 70 avec les travaux de E. R. Banks^[9] 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^[10].

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

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 6 états^[13].

[modifier] 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. toute les configurations mènent au bout d'un temps fini vers une même configuration uniforme)^[14],
savoir si un automate cellulaire de dimension $d\geq 2$ peut atteindre toutes les configurations après une étape (problème de la surjectivité)^[15],
savoir si un automate cellulaire de dimension $d\geq 2$ est réversible^[16].

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 $m$ présent initialement au centre, un motif $m'$ va apparaître au centre au bout d'un certain temps,
savoir si un motif $m$ peut apparaître arbitrairement tard dans l'évolution ou, au contraire, s'il existe un temps au delà duquel $m$ n'apparaît plus quelle que soit la configuration de départ.

[modifier] 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.

[modifier] Automates réversibles

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

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^[17] sont parmi les premiers à s'être intéressé 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).

[modifier] 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 $A$ ne peut pas être borné récursivement en fonction de la taille du voisinage de $A$ lorsque la dimension est 2 ou plus, alors qu'elle est bornée polynomialement en dimension 1 (un résultat récent^[18] montre même que la borne est linéaire).

[modifier] 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.

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 $t + 1$ en fonction de la génération $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.
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.
la technique du partitionnement : elle a été proposée par K. Morita et M. Harao^[19]. 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.

[modifier] 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é.

[modifier] 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

a i

égaux à 1.

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

$\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 $\oplus$ à une opération agissant cellule à cellule sur l'espace des configurations, la fonction globale $F δ$ 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 à $e$ (neutre de $\oplus$ ) sauf éventuellement en la cellule centrale.

[modifier] 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^[20]. Ces automates sont définis de la façon suivante :

$Q=\{0,\ldots,n-1\}$ ,
$\delta(x_1,x_2,\ldots) = \sum_i a_ix_i \pmod n$ où les coefficients $a i$ sont fixés et caractérisent l'automate.

L'exemple typique est celui où tous les coefficients $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 de la cellule et de ses deux voisines. Il suffit de connaître le comportement de cet automate sur la configuration $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 :

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

$0$ si $z > 0$ ou $z < - t$ ,
${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 $t$ étape partant d'une configuration quelconque $c$ :

$\sum_{i=0}^t c(i){{t}\choose {t-i}} \pmod 2$ .

[modifier] 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.

Automates sommatifs (totalistiques) tridimensionnels définis sur le voisinage rhomboédrique

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.

[modifier] Automates conservatifs

Cette section est vide, pas assez détaillée ou incomplète. Votre aide est la bienvenue !

[modifier] Le problème des classifications

Cette section est vide, pas assez détaillée ou incomplète. Votre aide est la bienvenue !

[modifier] 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 de se propager. Le jeu de la Vie en est un parfait exemple.

[modifier] 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 a 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ça 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.

[modifier] Généralisation et variations sur le modèle

Cette section est vide, pas assez détaillée ou incomplète. Votre aide est la bienvenue !

[modifier] Réseau de cellules

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

[modifier] 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.

[modifier] Autres

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

en utilisant des probabilités pour l'état d'une cellule à la génération suivante
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.

[modifier] Modélisation et Applications

On peut, en première approximation, 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 discrétisation sous forme d'automate cellulaire. 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 nombreuse 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).

[modifier] Modélisation en physique

Par nature, les automates cellulaires sont de bons candidats pour la modélisation en physique statistique, à condition bien sûr de discrétiser toutes les grandeurs. Parmi les modèles qui ont été très étudiés, on peut citer les automates de gaz sur réseau (lattice gaz automata en anglais) qui modélise 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 $2$ ) est due à J. Hardy, Y. Pomeau et O. Pazzis dans les années 70. Une seconde formulation, FHP, a été proposé dans les années 80 par U. Frisch, B. Hasslacher et Y. Pomeau : elle améliore la précédente en remplaçant le réseau de cellule $Z 2$ par un réseau hexagonal.

[modifier] 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 un 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

[modifier] 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 90 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 $\{v_1,\ldots,v_n\}$ , où $v i$ représentent la présence d'un véhicule roulant à la vitesse $v i$ ( $v 1$ représente l'arrêt) ;
le fonctionnement est schématiquement le suivant :

chaque véhicule accélère d'un cran (passe de $v i$ à $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,
la vitesse obtenue est diminuée d'un cran (passage de $v j$ à $v j - 1$ ) avec une certaine probabilité $p$ ,
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 ( $p = 0$ ). Si de plus $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.

[modifier] Voir aussi

[modifier] Articles connexes

[modifier] Domaines apparentés

[modifier] Règles particulières

[modifier] Liens externes

[modifier] 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°223 (Octobre 1970), p. 120-123
Stephen Wolfram, Universality and Complexity in Cellular Automata, Physica D n°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, no. 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°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.

[modifier] Notes et références

↑ John von Neumann, Arthur W. Burks, Theory of Self-Reproducing Automata, University of Illinois Press (1966)
↑ M. Morse et G. A. Hedlund, Symbolic Dynamics (American journal of Mathematics, vol. 60, 1938)
↑ 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°223 (Octobre 1970), p. 120-123
↑ Stephen Wolfram, Universality and Complexity in Cellular Automata, Physica D n°10 (Janvier 1984), p. 1-35
↑ Stephen Wolfram, A New Kind of Science, Wolfram Media (2002) - ISBN 1-57955-008-8
↑ John von Neumann, Arthur W. Burks, Theory of Self-Reproducing Automata, University of Illinois Press (1966)
↑ G. A. Hedlund, Endomorphisms and Automorphisms of the Shift Dynamical System (Mathematical Systems Theory, vol. 3, no. 4, 1969)
↑ 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
↑ Stephen Wolfram, A New Kind of Science, Wolfram Media (2002) - ISBN 1-57955-008-8
↑ 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.
↑ 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
↑ 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
↑ 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.
↑ O. Martin, A. Odlyzko et S. Wolfram, Algebraic Properties of Cellular Automata, Communications in Mathematical Physics (1984), n°93, p. 219

Automate cellulaire

Un article de Wikipédia, l'encyclopédie libre.

Sommaire

[modifier] Histoire

[modifier] Exemples

[modifier] Les automates cellulaires les plus simples

[modifier] Le jeu de la vie

[modifier] Tous les autres...

[modifier] Théorie des automates cellulaires

[modifier] Une définition formelle

[modifier] Systèmes dynamiques

[modifier] Modèle de calcul et constructions algorithmiques

[modifier] Automates cellulaires universels

[modifier] Universalité Turing

[modifier] Universalité intrinsèque

[modifier] Exemples

[modifier] Complexité

[modifier] Classes remarquables d'automates cellulaires

[modifier] Automates réversibles

[modifier] Reconnaissance

[modifier] Exemples

[modifier] Automates linéaires

[modifier] Définition

[modifier] Automates additifs

[modifier] Automates totalistiques

[modifier] Automates conservatifs

[modifier] Le problème des classifications

[modifier] Classification de Wolfram

[modifier] Classification d'Eppstein

[modifier] Généralisation et variations sur le modèle

[modifier] Réseau de cellules

[modifier] Asynchronisme

[modifier] Autres

[modifier] Modélisation et Applications

[modifier] Modélisation en physique

[modifier] Phénomènes biologiques

[modifier] Trafic routier

[modifier] Voir aussi

[modifier] Articles connexes

[modifier] Domaines apparentés

[modifier] Règles particulières

[modifier] Liens externes

[modifier] Bibliographie

[modifier] Notes et références

Views

Navigation

Contribuer

Rechercher

Autres langues