Vaisseau (automate cellulaire)

Un article de Wikipédia, l'encyclopédie libre.
Aller à : navigation, rechercher
Page d'aide sur l'homonymie Pour les articles homonymes, voir vaisseau.
Les fourmis
″The Ants", le plus petit vaisseau du Jeu de la vie

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.

Catégories[modifier | modifier le code]

On peut classer les vaisseaux dans 3 catégories:

Les vaisseaux orthogonaux[modifier | modifier le code]

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

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

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

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 N\ge 2(A+B)), on définit sa vitesse comme égale à c\cdot \frac {max(A,B)} {N}. Par exemple, une vitesse de \frac {c}{4} 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[modifier | modifier le code]

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
Glider.svg JdlV ship glider.5.gif Le planeur appelé "The Ants"[2]par John Conway \frac {c}{4} 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.png Game of life animated LWSS.gif LWSS \frac {c}{2} 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
HWSS fixe.jpg
HWSS en mouvement
Le HWSS \frac {c}{2} 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.

Structures associées[modifier | modifier le code]

Réflecteurs[modifier | modifier le code]

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.

Tagalongs et pushalongs[modifier | modifier le code]

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.

Apparenté au tagalong, le pushalong (terme anglais qui signifie à peu près pousseur) est un motif qui n'est pas un vaisseau par lui-même, mais qui peut être attaché devant un vaisseau pour en former un plus grand.

OWSS et flottilles[modifier | modifier le code]

Un OWSS est un vaisseau du type LWSS plus long que le HWSS. Or, le OWSS est trop gros pour exister car l'un de ses sparks (étincelles ou débris en français) est une ligne de 3 ou plus. Ces lignes ne disparaissent pas (ou du moins, pas à temps) et détruisent le OWSS. Il existe cependant un moyen pour stabiliser le OWSS: on peut empêcher ce débris d'exister avec deux vaisseaux plus petits (si ces vaisseaux sont eux-mêmes des OWSS, on peut les stabiliser avec des vaisseaux encore plus petits). Le OWSS devient alors un tagalong et crée un vaisseau en forme de double triangle appelé flottille

Une flottille où un OWSS (au centre) est escorté par deux HWSS.

Information[modifier | modifier le code]

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. Il existe des Portes logiques pour planeurs[3].

Dans les trois schémas qui suivent, une flèche est une file de planeurs, un cercle bleu indique que la file arrivant est détruite, un cercle jaune est un canon à planeurs, un cercle vert indique que la file rebondit(et la file arrivant est donc la même que celle sortant) et une étoile rouge indique que les deux files arrivant s'annihilent. Ces images ont été basculées à 45° pour être plus claires.

Annexes[modifier | modifier le code]

Articles connexes[modifier | modifier le code]

Liens externes[modifier | modifier le code]

  • (en) 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) Gliders in Life-Like Cellular Automata : compilation de vaisseaux dans divers automates cellulaires
  • (en) The 17c/45 Caterpillar spaceship : un vaisseau construit à partir de blocs séparé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) Paul's page of Conways Life Miscellany : de nombreuses figures du jeu de la vie avec leur code
  • Cornway's game of life : un site avec un excellent éditeur de figures de la vie, et des constructions à regarder évoluer.

Bibliographie[modifier | modifier le code]

  • Martin Gardner, Mathematical Games. The fantastic combinations of John Conway's new solitaire game "life", Scientific American n°223 (Octobre 1970), p. 120-123
  • William Poundstone, The recursive universe, Cosmic Complexity and the Limits of Scientific Knowledge, Oxford University Press (1987), p.78-89

Référence[modifier | modifier le code]

  1. Martin Gardner, Mathematical Games. The fantastic combinations of John Conway's new solitaire game "life", Scientific American n°223 (Octobre 1970), p. 120-123
  2. Interview de John Conway : http://www.youtube.com/watch?v=E8kUJL04ELA
  3. William Poundstone, The recursive universe, Cosmic Complexity and the Limits of Scientific Knowledge, Oxford University Press (1987), p.78-89