Automates cellulaires de dimension 1

Dans un automate cellulaire de dimension 1

1. L'ensemble des cellules est l'ensemble Z des entiers, les "cellules" sont (repérées par) des entiers.
2. Chaque cellule est à l'instant t dans un état s qui est un élément de l'ensemble S des états.
3. Le voisinage V de 0 est une suite ordonnée d'entiers V = (v₀, v₁, v₂, ...,v_n-1) de n entiers, le voisinage de toute cellule x s'en déduit et est x + V = (x+v₀, x+v₁, x+v₂, ..., x+v_n-1), dans le cas de certains automates, ce voisinage de x contient la cellule x.
4. Une fonction de transition locale f définie de Sⁿ vers S

À chaque instant t, pour chaque cellule x, les cellules y₀, ..., y_j... du voisinage x + V sont toutes dans des états s = (s₀, ..., s_j...). La fonction de transition locale f détermine l'état s' = f(s) = f(s₀, ..., s_j...) de la cellule x à l'instant suivant t+1.
Cette définition se généralise tout naturellement aux automates cellulaires sur Z^d.

Dans le cas d'un automate cellulaire à deux états |S|=2, on peut dresser le tableau suivant :

Nb d'éléments d'un voisinage :	1	2	3	4	5
Nb de valeurs possibles du voisinage :	2	4	8	16	32
Nb de fonctions de transitions différentes :	4	16	256	65536	4294967296

Les différentes lignes de la partie "Résultats" correspondent aux évolutions successives d'un automate cellulaire de dimension 1.
La première ligne est l'automate dans son état initial, les lignes suivantes correspondent aux états successifs l'automate.

Les automates réalisables dans cette page ont un ensemble S = {0, 1} de deux états seulement. Pour une meilleure lisibilité en mode texte, les états sont notés S = { "-", "X"}.
Dans cette page, les voisinages ont tous exactement trois éléments, mais les trois éléments d'un voisinage peuvent être choisis de diverses manières (dans des limites raisonnables en restant suffisamment près de la cellule).

Le nombre d'automates différents est 256 pour une définition d'un voisinage et une ligne initiale donnéess.
En changeant la définition des trois cases du voisinage on obtient donc un nombre plus élevé d'automates. En changeant la ligne initiale on augmente encore les possibilités.

L'un des voisinages les plus simple de B est ABC (trois cases successives), qui correspond à l'ensemble {-1, 0, 1}.
Si vous voulez essayer le voisinage A,B,C de T pour les positions suivantes : A__B_T_C, vous devez repérer les positions de A, B, C par rapport à T, ce qui donne {-5, -2, 2} dans l'exemple.

23 = 8 et 28 = 256.
Pour un voisinage défini sur trois cases, l'automate peut être décrit par une règle R que l'on code par un entier de 0 à 255 inclus :
en numération binaire, R a 8 chiffres au plus, par exemple R = 75_décimal = 0101011_binaire
Ce procédé permet d'associer une valeur c = 0 ou 1 (le chiffre binaire) à tout entier de v = 0 à 7 (la position de droite à gauche du chiffre dans R).
Exemples pour la règle R=75décimal = 0101011binaire ci-dessus :
Les chaînes sont lues de gauche à droite, le caractère "X" correspond à la valeur 1 et le caractère "-" correspond à 0.

1) "X--" correspond à v = 100_b = 4+0+0 = 4 et donc à c=0, le caractère central "-" de "X--" est remplacé par "-" sur la ligne suivante
2) "XXX" correspond à v = 111_b = 4+2+1 = 7 et donc à c=0, le caractère central "X" de "XXX" est remplacé par "-" sur la ligne suivante
3) "X-X" correspond à v = 101_b = 4+0+1 = 5 donc c = 0, le caractère central "-" de "X-X" est remplacé par "-" sur la ligne suivante
4) "-XX" correspond à v = 011_b = 3 donc c = 1, le caractère central "X" de "-XX" est remplacé par "X" sur la ligne suivante