Aller au contenu

Automate cellulaire/Automate unidimensionnel

Un livre de Wikilivres.

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.

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

[modifier | modifier le wikicode]

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 (où représente le nombre de motifs initiaux).

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).

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

Pour un étendue de 3 (par exemple la cellule et ses deux voisins immédiats), il y a 256 règles possibles (), 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

Pour un étendue de 4, il y a 65 536 règles possibles (), 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

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

Classement des règles

[modifier | modifier le wikicode]

Analyse indépendamment de l’étendue

[modifier | modifier le wikicode]

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 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 ;
    • et équivalent à , classe IIp ;
    • et équivalent à (en fait, l’inverse de la précédente), classe IIs ;
    • quel que soit l’étendue, les dernières règles sont équivalentes (, , , 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 , , , et , une cellule à l’état 0 restera à l’état 0.
  • de façon assez symétrique, pour les règles , , , et , une cellule à l’état 1 restera à l’état 1.

On remarque donc que :

  • l’on retrouve les deux extrêmes et ainsi que la règle stable 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

[modifier | modifier le wikicode]
é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