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.
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 23=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 28=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.
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 :
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).
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 | > 1017 |
3 voisins | 256 | 7 625 597 484 987 | > 1038 | > 1087 |
4 voisins | 65 536 | > 1038 | > 10154 | > 10436 |
5 voisins | 4 294 967 296 | > 10115 | > 10616 | > 102184 |
6 voisins | > 1019 | > 10347 | > 102466 | > 1010921 |
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.