C- Les autres types d'Automates Cellulaires

Le Jeu de la vie n'est qu'un type d'automate cellulaire parmi une infinité. Il est en effet possible de jouer sur l'ensemble des règles qui régissent l'univers de l'automate cellulaire.

Le paramètre le plus évident est le nombre de dimensions. Rien n'oblige en effet à considérer des environnements à deux dimensions. L'analyse théorique des automates cellulaires s'est essentiellement effectuée à partir d'automates à une dimension. En réduisant le nombre de dimensions, on limite l'explosion combinatoire, donc le nombre d'automates possibles. Si l'on considère le cas simple d'un voisinage de trois cellules, soit la cellule concernée et ses voisines de droite et de gauche, dans un automate à une dimension et deux états, il n'existe que 2 puissance 23 = 256 règles possibles. La représentation des automates à une dimension (soit une ligne), utilise la seconde dimension pour représenter le temps. À chaque génération, une nouvelle ligne est ajoutée au-dessous de la précédente, on peut visualiser ainsi la dynamique de ce type d'automate.

 

Exemple d'automate à une dimension (Triangle de Pascal)

Il est naturellement possible de créer des automates à trois dimensions voire plus.

Il est également possible de jouer sur la détermination du voisinage. Si l'on considère les automates à deux dimensions, les voisinages les plus courants sont 1 :

Par exemple, l'automate de Fredkin qui utilise un voisinage de Moore est basé sur la parité du voisinage. C'est un automate de type sommatif, c'est-à-dire que l'état des cellules dépend du nombre de voisins actifs, indépendamment de leur position. En l'occurrence, il n'y a reproduction que si la valeur de voisinage est impaire. Cet automate a la propriété remarquable de reproduire toute configuration de base en neuf exemplaires. La règle de Fredkin est généralisable à plus de deux dimensions.

Fredkin génération 0 et Fredkin génération 8

Il est également possible de jouer sur le nombre d'états. Rien n'oblige en effet à se cantonner aux deux états vie/mort. Brian's Brain par exemple, présenté par Brian Silverman en 1984 utilise trois états (vie/fantôme/mort) pour engendrer une grande diversité de planeurs complexes au sein de configurations graphiques étonnantes.

 

Brian's Brain

Des règles plus complexes sont imaginables. On peut par exemple construire des automates stochastiques dont les règles de transition intègrent une fonction de probabilité.

D'une manière générale, on peut construire tout type d'automate en jouant sur les règles structurelles et fonctionnelles. Les premières définissent la structure spatiale du réseau d'automates, soit son nombre de dimensions, le mode d'arrangement des cellules (carré, hexagonal... dans un automate à deux dimensions) et le mode de détermination du voisinage. Les secondes déterminent le nombre d'états et les règles de transition 2. Le choix de ces deux types de règles permet de construire un univers adapté à l'objectif recherché.


1. Shatten A., Cellular Automata, Institute of General Chemistry Vienna University of Technology, Austria, 1997.

2. Langlois A., Phipps M., Automates cellulaires. Application à la simulation urbaine, Hermès, 1997, pp. 17 et suivantes.