Automate cellulaire - Définition et Explications

Introduction

À 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 ( Un grille-pain est un petit appareil électroménager. Une grille écran est un...) 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 (En mathématiques, un ensemble E est dit fini si et seulement s'il existe un entier n et une...) et qui peut évoluer au cours du temps (Le temps est un concept développé par l'être humain pour appréhender le...). L'état d'une cellule au temps t+1 est fonction de l'état au temps t d'un nombre (La notion de nombre en linguistique est traitée à l’article « 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 (Les mathématiques constituent un domaine de connaissances abstraites construites à l'aide...) et en informatique (L´informatique - contraction d´information et automatique - est le domaine...) théorique, les automates cellulaires sont à la fois un modèle de système dynamique (En mathématiques, en physique théorique et en ingénierie, un 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 (Une définition est un discours qui dit ce qu'est une chose ou ce que signifie un nom. D'où la...) et la complexité (La complexité est une notion utilisée en philosophie, épistémologie (par...) que peuvent atteindre certains comportements macroscopiques : l'évolution dans le temps de l'ensemble (En théorie des ensembles, un ensemble désigne intuitivement une collection...) 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 (Un automate est un dispositif se comportant de manière automatique, c'est-à-dire sans...) 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 (La notion de voisinage correspond à une approche axiomatique équivalente à celle de la...) 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 :

(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 (Tableau peut avoir plusieurs sens suivant le contexte employé :) ci-dessus, décrivant la règle d'évolution.

Le jeu de la vie (Le jeu de la vie, automate cellulaire imaginé par John Horton Conway en 1970, est...)

Quelques étapes d'évolution du jeu de la vie (La vie est le nom donné :) à partir d'une configuration initiale choisie au hasard (Dans le langage ordinaire, le mot hasard est utilisé pour exprimer un manque efficient, sinon...).

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 (L'immigration désigne aujourd'hui l'entrée, dans un pays, de personnes...)
• 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 (Le poids est la force de pesanteur, d'origine gravitationnelle et inertielle, exercée par la...) plus important à certaines cases du voisinages qu'à d'autres (WeightedLife).

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 :

Le modèle des automates cellulaire offre donc un terrain d'exploration (L'exploration est le fait de chercher avec l'intention de découvrir quelque chose d'inconnu.) 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 (En informatique, un logiciel est un ensemble d'informations relatives à des traitements...) 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.