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)	Modèle:Rouge	Modèle:Rouge	-
Valeur suivante de la cellule (t+1)	0	0	Modèle:Vert
	0	1	Modèle:Vert
	1	0	Modèle:Vert
	1	1	Modèle:Vert

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 Modèle: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)	Modèle:Rouge1	Modèle:Rouge0	Modèle:Rouge1	Modèle:Rouge0	-
Valeur suivante de la cellule (t+1)	0	0	0	0	Modèle:Vert
	0	0	0	1	1
	0	0	1	0	2
	0	0	1	1	Modèle:Vert
	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	Modèle:Vert
	1	1	0	1	13
	1	1	1	0	14
	1	1	1	1	Modèle:Vert

É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	1Modèle:Rouge1	1Modèle:Rouge0	1Modèle:Rouge1	1Modèle:Rouge0	0Modèle:Rouge1	0Modèle:Rouge0	0Modèle:Rouge1	0Modèle:Rouge0	-
Valeur suivante de la cellule	0	0	0	0	0	0	0	0	Modèle:Vert
	…
	0	0	1	1	0	0	1	1	Modèle:Vert
	…
	0	0	0	1	1	1	1	0	30
	…
	1	1	0	0	1	1	0	0	Modèle:Vert
	…
	1	1	1	1	1	1	1	1	Modèle:Vert

Étendue de 4

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

Motif initial	1Modèle:Rouge11	1Modèle:Rouge10	1Modèle:Rouge01	1Modèle:Rouge00	1Modèle:Rouge11	1Modèle:Rouge10	1Modèle:Rouge01	1Modèle:Rouge00	0Modèle:Rouge11	0Modèle:Rouge10	0Modèle:Rouge01	0Modèle:Rouge00	0Modèle:Rouge11	0Modèle:Rouge10	0Modèle:Rouge01	0Modèle:Rouge00	-
Valeur suivante de la cellule	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	Modèle:Vert
	…
	0	0	0	0	1	1	1	1	0	0	0	0	1	1	1	1	Modèle:Vert
	…
	1	1	1	1	0	0	0	0	1	1	1	1	0	0	0	0	Modèle:Vert
	…
	1	1	1	1	1	1	1	1	1	1	1	1	1	1	1	1	Modèle:Vert

É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 Modèle: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 Modèle:Vert I Modèle:Vert IIp Modèle:Vert IIs Modèle:Vert I	Règle Classe Modèle:Vert I 1 2 Modèle:Vert IIp 4 5 6 7 8 9 10 11 Modèle:Vert IIs 13 14 Modèle:Vert I	Règle Classe