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

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.

[image]

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

[image]