Ce court document est une très brève introduction aux automates cellulaires, suffisante pour réaliser les quelques travaux pratiques demandés.

Soit $E$ l'ensemble fini des états possibles d'une cellule de l'automate. Par exemple, si les cellules n'ont que 2 états, on pourra prendre $E=\{vivant,mort\}$ ou $E={0,1}$.

L'état d'un automate de dimension $n$ est une application de ${\mathbb Z}^n$ dans $E$. Les éléments de ${\mathbb Z}^n$ sont appelées les cellules de l'automate. Chaque cellule a donc un état, qui est pris dans $E$. Par exemple, si l'automate est binaire, à une dimension, l'état de l'automate est une application qui à chaque nombre relatif associe par exemple 0 ou 1.

Les contraintes d'une implantation sur machine nécessitent de ne considérer que des automates ayant un nombre fini de cellule. Par exemple, nous pouvons considérer un automate cellulaire de dimension 2, de taille $5\times5$, dont chaque cellule est dans l'état 0 ou 1. Ceci correspond à un tableau de ce type :

Maintenant que nous avons défini l'état d'un automate, il nous reste à parler des règles de l'automate, qui indiquent à chaque instant comment évoluent les cellules.

Voici un exemple de table de transitions pour un automate cellulaire de dimension 1, dont les cellules sont dans l'état blanc ou noir (les règle ont été numérotées) :

Finalement, un automate cellulaire complet est donné par :

• sa topologie, son voisinage (nous considérerons pour notre part des automates cellulaires de dimension 1 ou de dimension 2 à grille carrée)
• son état initial, c'est à dire l'état initial de chaque cellule de l'automate
• sa table de transition qui permet de calculer l'état futur de l'automate.

Simuler un automate cellulaire consiste à tracer sur un écran graphique l'état de l'automate à des dates successives.

Par exemple, considérons l'automate à une dimension, formé de 11 cellules, dans l'état initial suivant :

Supposons que sa table de transitions soit celle donnée plus haut. Alors, nous pouvons simuler l'automate en représentant sont état initial sur la première ligne, l'état suivant sur la seconde ligne etc… Voici les 9 premiers états de l'automate.

Pour réaliser cette simulation, nous avons dû considérer des conditions limites, permettant de traiter le cas des cellules extrêmes. Nous avons ici choisi de considérer qu'en dehors du domaine, les cellules sont blanches. Nous aurions aussi pu considérer que le bord gauche est relié au bord droit, ou toute autre règle de notre choix.

Sur les automates cellulaires (Ancienne version au format PDF (plus à jour))