Vaisseau (automate cellulaire)
From Wikipedia, the free encyclopedia
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. Un vaisseau ressemble à un puffeur, à ceci près que contrairement à ce dernier, un vaisseau n'émet par définition pas de débris. Aussi, on peut transformer un puffeur en vaisseau en arrivant à détruire ses débris comme pour l'écologiste.
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.
Les vaisseaux orthogonaux
On peut classer les vaisseaux dans 3 catégories:
On parle de vaisseau orthogonal pour décrire les vaisseaux se déplaçant vers l'un des 4 points cardinaux. Le LWSS fait partie de cette catégorie. Ce sont les plus répandus en variété.
Les vaisseaux diagonaux
On parle de vaisseau diagonal pour décrire les vaisseaux se déplaçant selon une diagonale. Le planeur fait partie de cette catégorie. Beaucoup peuvent être considérés comme des "tagalongs" (voir plus bas) du planeur. Ce sont les premiers à avoir été trouvés.
Les vaisseaux obliques
On parle de vaisseau oblique, ou vaisseau-cavalier (knightship en anglais) pour décrire les vaisseaux ne se déplaçant ni orthogonalement, ni diagonalement. Seuls deux vaisseaux de ce type sont connus: gemini et un dérivé de celui-ci.
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 cases horizontalement et de cases verticalement sur 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. C'est par exemple le cas du planeur.
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 | Vitesse | Commentaire | année de découverte | |
|---|---|---|---|---|---|
| fixe | en déplacement | ||||
 |
 |
Le planeur appelé "The Ants"[2]par John Conway | 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, pour une vitesse de C/4. | 1970 | |
 |
 |
LWSS | Trois autres vaisseaux se déplacent horizontalement (ou verticalement) de deux cases toutes les quatre générations, pour une vitesse de C/2. Ils portent en anglais le nom de Light, Medium et Heavy Weight Spaceships (littéralement « vaisseaux de poids léger, moyen et lourd »), généralement abrégés en LWSS, MWSS et HWSS. | 1970 | |
 |
 |
Le HWSS | Le HWSS est le plus gros vaisseau de la famille du LWSS. | 1970 | |
Depuis, de nombreux autres vaisseaux furent découverts, se déplaçant éventuellement à des vitesses différentes.
.jpg)
.jpg)
.jpg)
