Automates cellulaires

Création en cours.

Ce projet avait pour but d'étudier le fonctionnement des automates cellulaires et les caractéristiques particulières que l'on peut retrouver chez certains.

Définitions

Définition simple

Un automate cellulaire est une grille régulière dont les cases sont appelées « cellules ». Chacune a un « état » parmi un ensemble fini. L'état d'une cellule au « tour » t+1 est définit en fonction de cet état et celui de l'ensemble fini de cellules « voisinage » au tour t, par la « règle » de l'automate cellulaire. Lorsque toutes les cellules ont été mises à jour, on parle de « génération ».

Définition formelle

Un automate cellulaire $A$ est définit par le 4-uplet $(d,Q,V,\delta )$ tel que :

• $d$ est un entier positif, la dimension de $A$. Son réseau est donc $\mathbb {Z} ^{d}$
• $Q$ est l'ensemble fini des états des cellules de $A$
• $V\subseteq \mathbb {Z} ^{d}$, un sous-ensemble fini du réseau, le voisinage. $V=\{v_{1},\ldots ,v_{a}\}$
• $\delta :Q^{a}\rightarrow Q$ est la règle locale avec $a=|V|$

On peut donc définir la fonction globale d'évolution de l'automate $F_{\delta }:Q^{\mathbb {Z} ^{d}}\rightarrow Q^{\mathbb {Z} ^{d}}$ définit par $F_{\delta }(c)=z\mapsto \delta {\bigl (}c(z+v_{1}),\ldots ,c(z+v_{a}){\bigr )}$ pour tout $c\in Q^{\mathbb {Z} ^{d}}$

Classifications

Bien que les deux classifications qui sont décrites ci-dessous peuvent être retrouvées dans les travaux de certains chercheurs, il est commun de décrire un automate en fonction de leurs caractéristiques particulières sans pour autant les séparer en classes.

Classification de Wolfram

Stephen Wolfram classe les automates cellulaires en 4 classes selon leur comportement avec des configurations initiales aléatoires :

1. Stable : Après un certain nombre de générations, une configuration se répète à l'infini.
2. Cyclique : Après un certain nombre de générations, une série de configurations se répètent périodiquement.
3. Chaotique : Comportement chaotique et génération de motifs apériodiques.
4. Complexe : Apparition de structures complexes possédants divers propriétés comme la capacité de se mouvoir ou de se préserver malgré des perturbations.

L'une des principales critiques de cette classification réside dans son incapacité à déterminer si un automate cellulaire est Turin-universel, venant du fait que Wolfram ne définit la classe qu'à partir de configurations initiales aléatoires, mais pas de structure particulière créée spécifiquement. Malgré cela, cette classification reste la plus étudiée.

Christopher Langton propose d'envisager ces classes dans un continuum.

Classification d'Eppstein

Il existe une deuxième classification, proposée par David Eppstein. Les automates sont séparés en 4 classes :

1. Expansion obligatoire : N'importe quel motif initial s'étend indéfiniment dans toutes les directions.
2. Expansion impossible : Aucun motif ne peut s'étendre au-delà de ses limites initiales.
3. Contraction impossible : Les motifs ne s'étendent pas forcément indéfiniment, mais ne peuvent jamais se réduire en-deçà de leur limites initiales.
4. Expansion et contraction possibles : Seuls ces cas peuvent contenir des vaisseaux.

À l'heure actuelle, les automates qui ont été prouvés Turing-universels appartiennent tous à la 4ème classe. Cependant il n'a pas été démontré que les autres classes ne peuvent pas contenir d'automate Turing-universel puisqu'il existe d'autres façons de transmettre des informations que les vaisseaux.

Les familles d'automates cellulaires célèbres

Il existe de nombreuses familles d'automates cellulaires, mais nous n'en verrons que deux ici.

Les automates cellulaires élémentaires

Cette famille est la plus simple des automates cellulaires. Ses membres n'ont qu'une dimension et deux états. Le voisinage d'une cellule est composé de celles directement à sa droite et sa gauche et d'elle-même.

Puisque le voisinage prend 3 cellules et que chacune d'elles a un état parmi 2, on a $2^{3}=8$ motifs possibles. Pour chaque motif il y a 2 résultats possibles, donc $2^{8}=256$ règles possibles pour un automate cellulaire de cette famille. Depuis les travaux de S. Wolfram sur cette famille, chacune de ces règles est nommée par le résultat de ses motifs convertit en décimal.