Vaisseau (automate cellulaire)
Un article de Wikipédia, l'encyclopédie libre.
Dans un automate cellulaire, un motif fini est nommé vaisseau, ou navire, s'il réapparait au bout d'un certain nombre de générations dans une position différente.
Le concept de vaisseau a été introduit par John Horton Conway pour le Jeu de la vie — sous le nom anglais de spaceship, vaisseau spatial[1]. Bien que cette notion s'applique a priori à n'importe quel automate cellulaire, elle a été surtout étudiée dans le Jeu de la vie, qui en a sans doute produit les spécimens les plus spectaculaires et les plus nombreux.
Sommaire |
[modifier] Vitesse
En premier lieu, le nombre minimum de générations nécessaires à la réplication du motif en un autre endroit est nommé la période du vaisseau.
Pour un automate cellulaire, il existe une vitesse maximale à laquelle un effet peut se propager et qui dépend des règles utilisées (par exemple, pour le Jeu de la vie qui ne prend en compte pour la génération suivante d'une cellule que celles qui lui sont strictement adjacentes, cette vitesse maximale est d'une cellule par génération). Historiquement, Conway a nommé cette vitesse la « vitesse de la lumière », et l'a notée c — par analogie à la vitesse de la lumière du monde physique, théoriquement indépassable.
Pour un automate cellulaire à deux dimensions, si un vaisseau se déplace de A cases horizontalement et de B cases verticalement sur N générations (on peut d'ailleurs montrer que 
), on définit sa vitesse comme égale à 
. Par exemple, une vitesse de 
signifie que le vaisseau se déplace d'une cellule (horizontalement, verticalement, ou les deux en même temps) toutes les quatre générations.
[modifier] Exemples
Dès les débuts du Jeu de la vie en 1970, quatre vaisseaux furent découverts car ils apparaissent relativement spontanément dans beaucoup de configurations :
| Image | Nom | Commentaire | |
|---|---|---|---|
| fixe | en déplacement | ||
 |
 |
Le planeur | C'est le plus petit vaisseau du jeu de la vie : cinq cellules contenues dans un carré de trois cellules sur trois. Il se déplace d'une case en diagonale toutes les quatre générations. |
 |
 |
LWSS | Trois autres vaisseaux se déplacent horizontalement (ou verticalement) de deux cases toutes les quatre générations. Ils portent en anglais le nom de Light, Medium et Heavy Weight Spaceships (littérallement « vaisseaux de poids léger, moyen et lourd »), généralement abrégés en LWSS, MWSS et HWSS. |
Depuis, de nombreux autres vaisseaux furent découverts, se déplaçant éventuellement à des vitesses différentes.
[modifier] Structures associées
[modifier] Réflecteurs
Un motif qui, lorsqu'il est atteint par un vaisseau, produit une copie de ce vaisseau se déplaçant dans un direction différente est appelée un réflecteur.
[modifier] Tagalongs
Un tagalong (terme anglais signifiant à peu-près « suiveur ») est un motif qui n'est pas un vaisseau par lui-même, mais qui peut être attaché derrière un vaisseau pour en former un plus grand. Souvent, plusieurs tagalongs peuvent être attachés successivement, pouvant même rattacher plusieurs vaisseaux distincts.
[modifier] Information
Les vaisseaux peuvent aussi être utilisés pour transmettre de l'information. Par exemple, dans le Jeu de la vie, le planeur peut servir à cette fonction.
[modifier] Annexes
[modifier] Articles connexes
[modifier] Liens externes
- Spaceships in Conway's Game of Life : copie d'une série de messages postés par David L. Bell sur le groupe comp.theory.cell-automata en 1992, faisant le tour de l'état de l'art de l'époque (en anglais).
- Gliders in Life-Like Cellular Automata : compilation de vaisseaux dans divers automates cellulaires (en anglais).
- The 17c/45 Caterpillar spaceship : un vaisseau construit à partir de blocs sépararés, de période 17c/45, en 2004. Haut de 330 721 cellules, large de 4 195 et comptant à peu près 12 millions de cellules, il s'agit à l'heure actuelle du plus grand objet jamais créé pour le Jeu de la vie (en anglais).
[modifier] Bibliographie
- Martin Gardner, Mathematical Games. The fantastic combinations of John Conway's new solitaire game "life", Scientific American n°223 (Octobre 1970), p. 120-123
[modifier] Référence
- ↑ Martin Gardner, Mathematical Games. The fantastic combinations of John Conway's new solitaire game "life", Scientific American n°223 (Octobre 1970), p. 120-123
