Vaisseau (automate cellulaire)

Vaisseau (automate cellulaire)
Page d'aide sur l'homonymie Pour les articles homonymes, voir vaisseau.
Le « Planeur », 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.

Sommaire

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

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
Glider.svg JdlV ship glider.5.gif 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, pour une vitesse de C/4.
LWSS.png Game of life animated LWSS.gif 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.
HWSS fixe.jpg
HWSS en mouvement
Le HWSS Le HWSS est le pus gros vaisseau de la famille du LWSS.

Depuis, de nombreux autres vaisseaux furent découverts, se déplaçant éventuellement à des vitesses différentes.

Structures associées

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.

Tagalongs et pushalongs

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

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

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[2].

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

Articles connexes

Liens externes

  • (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

  • 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

  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. William Poundstone, The recursive universe, Cosmic Complexity and the Limits of Scientific Knowledge, Oxford University Press (1987), p.78-89

Wikimedia Foundation. 2010.

Contenu soumis à la licence CC-BY-SA. Source : Article Vaisseau (automate cellulaire) de Wikipédia en français (auteurs)

Игры ⚽ Нужен реферат?

Regardez d'autres dictionnaires:

  • Automate Cellulaire — À gauche, une règle locale simple : une cellule passe d un état (i) au suivant (i+1) dans le cycle d états dès que i+1 est présent dans au moins 3 cellules voisines. À droite, le résultat (complexe !) de l application répétée de cette… …   Wikipédia en Français

  • Canon (Automate Cellulaire) — Pour les articles homonymes, voir Canon. Le canon à planeurs Gosper, qui émet des planeurs …   Wikipédia en Français

  • Automate cellulaire — À gauche, une règle locale simple : une cellule passe d un état (i) au suivant (i+1) dans le cycle d états dès que i+1 est présent dans au moins 3 cellules voisines. À droite, le résultat (complexe) de l application répétée de cette règle… …   Wikipédia en Français

  • Canon (automate cellulaire) — Pour les articles homonymes, voir Canon. Le canon à planeurs de Gosper, créé par Bill Gosper, qui émet des planeurs …   Wikipédia en Français

  • Immigration (automate cellulaire) — Immigration est un automate cellulaire. Description Immigration fonctionne exactement de la même façon que le jeu de la vie, à ceci près qu il possède trois états, dont deux « vivants ». Une cellule morte y naît à l étape suivante si… …   Wikipédia en Français

  • Oscillateur (automate cellulaire) — Pour les articles homonymes, voir Oscillateur. Dans un automate cellulaire, un motif fini est appelé oscillateur s il retourne à son état d origine, dans la même orientation et à la même position, au bout d un nombre fini de générations. Sommaire …   Wikipédia en Français

  • Mathusalem (automate cellulaire) — Pour les articles homonymes, voir Mathusalem (homonymie). Le pentomino R. Dans le jeu de la vie, un mathusalem est un motif qui met un certain moment avant de se stabiliser en une constellation de débris plus ou moins importante …   Wikipédia en Français

  • Spacefiller (automate cellulaire) — Un exemple de spacefiller Un spacefiller (de l anglais spacefiller, remplisseur d espace) est une figure qui grossit exponentiellement en étendant un agar (un oscillateur ou une structure stable infini et bidimensionnel). Le premier spacefiller s …   Wikipédia en Français

  • Jardin d'Éden (automate cellulaire) — Pour les articles homonymes, voir Jardin d Éden. Dans un automate cellulaire, un motif fini est nommé jardin d Éden s il ne possède aucun prédécesseur. C’est à dire qu il n existe aucune configuration qui permette d atteindre un jardin d Éden… …   Wikipédia en Français

  • Structure stable (automate cellulaire) — Dans un automate cellulaire, un motif fini est appelé structure stable s il ne change pas d une génération à l autre. Ils apparaissent spontanément et sont variés par leur forme, leur taille et leur nombre. Sommaire 1 Définition 2 Exemples 3… …   Wikipédia en Français

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”