Automate cellulaire/Automate unidimensionnel

Sur une grille dimensionnelle, un automate − ses règles, son comportement, son destin − est simplifié et permet une analyse plus facile. Pour faciliter encore l’analyse, chaque cellule de cette grille ne prendra que deux valeurs.

Règles

Préambule

Le nombre de valeurs à t+1 de l’état d’une cellule dépend de la règle choisie. Il existe une infinité de règles possibles.

La règle la plus simple est : la valeur reste identique quel que soit t. Mais un règle peut être infiniment plus complexe :

• au niveau de l’étendue, elle peut prendre en compte l’intégralité de la grille (en cas de grille finie),
• elle peut intégrer des probabilités,
• elle peut même intégrer des paramètres non mathématiques,
• etc.

Selon l’étendue

On peut commencer par classer ces règles par l’étendue (nombre de cellules, ici la largeur) prise en compte. Plus l’étendue sera large, plus le nombre de règle sera important. Le nombre de règle en fonction du l’étendue x est de $2^{2^{x}}$ (où $2^{x}$ représente le nombre de motifs initiaux).

Étendue de 1

Pour un étendue de 1, il y a 4 règles possibles (même si on peut imaginer une infinité de formulations) :

Motif initial (t)	1	0	-
Valeur suivante de la cellule (t+1)	0	0	0
	0	1	1
	1	0	2
	1	1	3

Sauf mention contraire, par la suite on ne considérera que la cellule concernée (celle dont on recherche l’état à t+1). De façon arbitraire et pour faciliter la compréhension, on considérera que la cellule concernée est la cellule centrale ou celle immédiatement à sa gauche en cas d’étendue pair. Pour faciliter la visualisation, celle-ci en colorée en rouge dans la première ligne des tableaux. Cette convention est purement arbitraire, on pourrait très bien imaginer qu’une cellule n’est pas influencé par ses voisines immédiate mais par des cellules situées ailleurs (dans ce cas, on sortirait de la loi de voisinage de Moore).

Étendue de 2

Pour un étendue de 2 (par exemple les deux voisins immédiats, ou bien la cellule concernée et un de ses voisines), il y a 16 règles possibles. Pour simplifier leur dénomination, le nom de la règle est désigné par les états binaire en base décimale (dernière colonne).

Motif initial (t)	11	10	01	00	-
Valeur suivante de la cellule (t+1)	0	0	0	0	0
	0	0	0	1	1
	0	0	1	0	2
	0	0	1	1	3
	0	1	0	0	4
	0	1	0	1	5
	0	1	1	0	6
	0	1	1	1	7
	1	0	0	0	8
	1	0	0	1	9
	1	0	1	0	10
	1	0	1	1	11
	1	1	0	0	12
	1	1	0	1	13
	1	1	1	0	14
	1	1	1	1	15

Étendue de 3

Pour un étendue de 3 (par exemple la cellule et ses deux voisins immédiats), il y a 256 règles possibles ($2^{2^{3}}$), par exemple :

Motif initial	111	110	101	100	011	010	001	000	-
Valeur suivante de la cellule	0	0	0	0	0	0	0	0	0
	…
	0	0	1	1	0	0	1	1	51
	…
	0	0	0	1	1	1	1	0	30
	…
	1	1	0	0	1	1	0	0	204
	…
	1	1	1	1	1	1	1	1	255

Étendue de 4

Pour un étendue de 4, il y a 65 536 règles possibles ($2^{2^{4}}$), par exemple :

Motif initial	1111	1110	1101	1100	1011	1010	1001	1000	0111	0110	0101	0100	0011	0010	0001	0000	-
Valeur suivante de la cellule	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0
	…
	0	0	0	0	1	1	1	1	0	0	0	0	1	1	1	1	3855
	…
	1	1	1	1	0	0	0	0	1	1	1	1	0	0	0	0	61680
	…
	1	1	1	1	1	1	1	1	1	1	1	1	1	1	1	1	65535

Étendue N

On pourrait continue ainsi de suite jusqu’à une étendue infinie.

Classement des règles

Analyse indépendamment de l’étendue

On peut classer ces règles en fonction de l’état final (Classification de Stephen Wolfram, 1983) :

• structure « fixe », toutes les cellules sont à 1 ou 0, classe I
• structure « stable » et structure « périodique », classe II
  • structure « stable », classe IIs
  • structure « périodique », classe IIp
• structure « chaotique », classe III
• aucune des structures précédentes, classe IV

Dans chaque tableau, les quatre règles colorées en vert sont celles pour laquelle l’état des cellules voisines ne sont pas pris en compte. Par exemple, pour la règle $204_{e}3$ quel que soit l’état des cellules voisines, la cellule concernée reste dans son état originel. On est donc dans une règle de classe I ou II.

• Ces quatre règles peuvent donc se réduire à celle d’une étendue unitaire :
  • quel que soit l’étendue, les règles 0 sont équivalentes, classe I ;
  • $3_{e2}$ et $51_{e3}$ équivalent à $1_{e1}$, classe IIp ;
  • $12_{e2}$ et $204_{e3}$ équivalent à $2_{e1}$ (en fait, l’inverse de la précédente), classe IIs ;
  • quel que soit l’étendue, les dernières règles sont équivalentes ($3_{e1}$, $15_{e2}$, $255_{e3}$, etc.), classe I.

On peut aussi facilement distinguer les règles qui auront tendance à mener (destin prévisible) vers une grille uniforme de 0 ou de 1 (classe I) ou au minimum stable (classe II). Par exemple :

• pour les règles $0_{e2}$, $4_{e2}$, $8_{e2}$, et $12_{e2}$, une cellule à l’état 0 restera à l’état 0.
• de façon assez symétrique, pour les règles $12_{e2}$, $13_{e2}$, $14_{e2}$, et $15_{e2}$, une cellule à l’état 1 restera à l’état 1.

On remarque donc que :

• l’on retrouve les deux extrêmes $0_{e2}$ et $15_{e2}$ ainsi que la règle stable $12_{e2}$ et on en découvre de nouvelles.
• − quelle que soit l’étendue − il y aura toujours la moitié des règles dans ce cas (les automates cellulaires semblent donc moins imprévisibles que prévu).

Tableau pour les étendues de 1 à 3

étendue de 1	étendue de 2	étendue de 3
Règle Classe 0 I 1 IIp 2 IIs 3 I	Règle Classe 0 I 1 2 3 IIp 4 5 6 7 8 9 10 11 12 IIs 13 14 15 I	Règle Classe