L’Automate Cellulaire du "jeu de la vie"
Le "jeu de la vie" est un automate emblématique, il est à la fois très simple par ses règles et complexe par sa dynamique. De ce fait, Il fut très étudié (Conway, William Gosper, Alvy Ray Smith, etc). En particulier il possède des propriétés mathématiques importantes : celle de calculateur universel, de plus, c’est le plus simple automate cellulaire de dimension 2, ayant la propriété d’auto-reproduction (sachant qu’il n’y en a que trois connus, celui de von Neumann à 19 états et celui de Codd à 8 états).
Description
Chaque cellule est un automate binaire à fenêtre, c’est-à-dire que chaque cellule peut prendre deux états : 0 ou 1. L’état 0 (en blanc) signifie "cellule morte" et l’état 1 (en rouge) signifie "cellule en vie". Le changement d’état d’une cellule (sa fonction de transition) ne dépend que de l’état de la cellule et du nombre de voisins vivants. L’état change si ce nombre est compris dans un certain intervalle (la fenêtre).
On utilise le voisinage à 8 voisins (dit voisinage de Moore).
La fonction de transition est définie de la manière suivante :
- une cellule morte (0) devient vivante (1) si trois de ses voisins sont vivants (naissance)
- une cellule reste vivante si 2 ou 3 de ses voisins sont vivants sinon elle meurt.
La fonction de transition peut aussi se représenter par un graphe comme ci-dessous :
Comportement
Le jeu de la vie a une dynamique intermédiaire entre un comportement organisé et chaotique.
Les configurations à long terme sont pratiquement impossibles à prévoir, on constate néanmoins des formes simples qui restent fixes lorsqu’elles apparaissent, comme un carré de 2 sur 2, ou d’autres qui oscillent selon un cycle très court, comme une ligne de 3 cellules qui oscille entre position verticale et horizontale. Mais ces formes simples ne sont pas définitives. En effet, elles peuvent entrer en collision avec des formes mobiles qui possèdent un cycle assez court, tout en se déplaçant et qu’on appelle des planeurs. Les collisions produisent d’autres formes ce qui complexifie le comportement global et le rend pratiquement imprévisible.
This article last updated samedi 29 avril 2006. par Patrice Langlois