Automate cellulaire

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

Vous avez de nouveaux messages (diff^?).

Étudiés en mathématiques et en théorie de la calculabilité, 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 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 est fonction de l'état au temps t-1 d'un nombre fini de cellules appelé son « voisinage ». À chaque nouvelle unité de temps, les mêmes règles sont appliquées pour 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.

[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, Konrad Zuse publia Rechnender Raum (« Calculer l'espace ») [2] 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 [3].

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

[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 pouvant être simulés sur une telle grille.

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.

Cette règle est souvent 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

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

[modifier] Autres automates cellulaires

De nombreux automates cellulaires ont été développés, souvent en dérivant le modèle du jeu de la vie, comme entre autres :

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

Un logiciel qui sait calculer les générations pour une très grande partie de ces automates cellulaires : Mirek's Cellebration.

[modifier] Classification

[modifier] Traitement parallèle ou série

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. C'est le cas du jeu de la vie, par exemple.
Pour les automates cellulaires à traitement série, seul l'état d'une ou plusieurs cellules est mis à jour. On retrouve ce traitement dans la fourmi de Langton.

[modifier] Dimensions

La deuxième possibilité de classification, et peut-être la plus évidente, repose sur le nombre de dimensions de la grille utilisée.

Couramment, l'automate cellulaire possède une ou deux dimensions.

Plus rarement, on trouve des automates cellulaires à trois dimensions, mais peu de règles ont été étudiées, principalement pour des contraintes de représentation, d'espace mémoire et de temps machine.

Il est en théorie possible de bâtir des automates cellulaires possédant un nombre de dimensions plus grand que trois, mais cette voie a rarement été explorée.

[modifier] Nombre d'états

Une troisième classification concerne le nombre d'états que peut prendre une cellule. Au minimum, une cellule peut prendre deux états (vivante ou morte, c'est le cas du Jeu de la vie par exemple), mais il est possible de définir des règles avec plus d'états (le constructeur de von Neumann, le premier automate cellulaire, fonctionnait avec pas moins de 29 états distincts).

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

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] Automate cellulaires universels

On dit qu'un automate cellulaire est universel s'il est lui-même une machine de Turing universelle, c'est à dire qu'il est capable de simuler toute autre machine de Turing. Le jeu de la vie par exemple est universel.

Cette universalité est un point de recherche important dans le domaine des automates cellulaires.

[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 non pas les règles d'un automate cellulaire mais le devenir général de configurations initialement aléatoires. Il classa les possibilités d'évolution en quatre classes, selon un ordre arbitraire de la moins intéressante à la plus digne d'intérêt :

Classe I : n'importe quelle 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.
Classe III : comportement chaotique. Pour un tel automate cellulaire, le nombre d'informations nécessaires pour prédire son état augmente avec le nombre d'itérations. Il s'agit également de la seule classe d'automate cellulaire réversibles, à savoir qu'à partir d'un état quelconque, il est toujours possible de retrouver quel était l'état précédent.
Classe IV : présence de structures complexes. Il s'agit du seul cas non trivial d'automates cellulaires non réversibles. 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 une machine de Turing universelle ; 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 peuvent sembler universels, même s'il n'est pas prouvé que tous les automates cellulaires qui y répondent le sont forcément. 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

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

en changeant la façon dont la grille est pavée, par exemple avec des triangles equilatéraux.
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] Automates cellulaires naturels

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

Les motifs de certains coquillages, comme les cônes et les cymbiolae, sont générés comme des automates cellulaires naturels. 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.

[modifier] Voir aussi

[modifier] Articles connexes

[modifier] Liens externes

[modifier] Bibliographie

[1] John von Neumann, Arthur W. Burks, Theory of Self-Reproducing Automata, University of Illinois Press (1966)
[2] Konrad Zuse, Rechnender Raum, Schriften zur Datenverarbeitung Band, Friedrich Vieweg & Sohn, Braunschweig (1969)
[3] Martin Gardner, Mathematical Games. The fantastic combinations of John Conway's new solitaire game « life », Scientific American n°223 (Octobre 1970), p. 120-123
[4] Stephen Wolfram, Universality and Complexity in Cellular Automata, Physica D n°10 (Janvier 1984), p. 1-35
[5] Stephen Wolfram, A New Kind of Science, Wolfram Media (2002) - ISBN 1579550088

Récupérée de « http://fr.wikipedia.org../../../a/u/t/Automate_cellulaire.html »

Catégorie : Automate cellulaire