Accueilretour
précédentsuivant

Configurations indéfiniment croissantes

Origines

"Blinkers"

Jardins d'Éden

Navires

Canons...

  Canons, puffers

  Gosper gun

  1ers puffers

  Extenseur

  Rakes

"Breeders"

Machines

Métacellules

Documents

 Une population peut-elle augmenter indéfiniment au jeu de la vie, et à quelle vitesse ? En 1970, John Conway offrait un prix de $ 50 (!) à qui proposerait un exemple de configuration indéfiniment croissante [1].

Canons, "puffers", etc.

Pour construire une telle configuration, deux pistes viennent à l'esprit :
  • on peut penser à un dispositif qui donne périodiquement naissance à des navires. Ceux-ci s'éloignent sans cesse de la "fabrique", et leur nombre n'arrête pas d'augmenter, donc aussi le chiffre de la population.
    On parle de "canons" ou "lance-glisseurs".
  • on peut aussi envisager une structure qui se déplace dans l'espace, mais en laissant derrière elle une "traînée" (continue ou non) de cellules (ou groupes) stables.
    On désigne par puffers [2] les représentants de cette catégorie.

Le Gosper gun

Voici le premier représentant connu de canon lance-glisseurs. Il a été proposé dès 1970 par R. W. "Bill" Gosper, qui remporta ainsi le prix offert.

Gosper's gun

Remarquablement simple, il ne comporte initialement que 36 cellules [3]. À la 15ème génération, il émet un glisseur qui s'éloigne vers le bas et la droite. Les glisseurs suivants sont émis toutes les 30 générations, ce qui correspond à la période de la partie principale (le "canon").

Gosper's glider gun

Étonnamment, il est possible de "synthétiser" ce lance-glisseurs : en disposant judicieusement 8 glisseurs dans le plan, leurs collisions mutuelles donneront naissance au Gosper gun. On sait synthétiser bien d'autres objets à partir de glisseurs convenablement arrangés : natures mortes, blinkers, ... Les glisseurs apparaissent comme une des "briques" fondamentales pour des constructions élaborées dans le Jeu de la vie.

synthèse du Gosper gun avec huit glisseurs

On connaît maintenant des "canons" de périodes d'émission 14 [4], 15, 23, 30, ..., 360, ..., 30 360 ! Cette dernière configuration de 368 cellules, inventée par D. Leitner en 1998, semble à première vue un blinker de faible période. Une observation plus attentive révèle, de temps à autre, l'émission d'un glisseur bien esseulé.

Il existe aussi des lance-glisseurs pseudo-aléatoires, d'émission apériodique. C'est ce type de canon qui permet d'obtenir des taux de croissance "exotiques".

haut de page

Les premiers puffers

C'est le même Bill Gosper qui proposa en 1971 les deux premiers exemples de puffers.

Le tout premier est composé de 44 cellules et avance transversalement à la vitesse de c/2. La "locomotive" est de période 128. Le voici (orienté pour un déplacement vers le haut)...

1st puffer

... ainsi que la traînée qu'il laisse derrière lui :

génération 1056 - déplacement vers la droite

Le second est encore plus simple avec ses 22 cellules et sa loco de période 140. Mais sa traîne est extrêmement "poussiéreuse", mettant plus de 5500 générations à se stabiliser et expulsant au passage quelques glisseurs.

2nd puffer

En 1971, Charles R. Corderman a crée le switch engine avec seulement 8 cellules (version instable) ou 11 cellules (avec "stabilisateur") :

Corderman's puffer

Les trois cellules à droite constituent le stabilisateur. Sans elles, la machine cesse d'émettre des glisseurs après 3911 générations.

haut de page

L'extenseur et le chasse-neige

Voici une autre configuration intéressante datant de 1992, l'extenseur.

extenseur

Représenté ici après 200 générations, on dirait un navire (de type transversal) dont la "tête" et la "queue" s'éloignent l'une de l'autre (à la vitesse c/4), ce qui l'allonge à l 'infini.

Le chasse-neige quant à lui a été construit en 1993 sur la base d'un navire diagonal de vitesse c/4 également.

chasse-neige

La génération n°100 représentée ici montre bien les "traces de chenilles" stables qu'il laisse derrière lui lors de sa progression.

haut de page

Rakes

Dans certains cas, le puffer engendre des navires plutôt que des configurations immobiles. On se retrouve ainsi avec un train de navires qui suit le véhicule principal, à la même vitesse ou plus lentement.

On parle dans ce cas de rake (râteau). Le premier a été construit en 1971 par un auteur inconnu [5]. Il n'est composé que de 65 cellules :

le spacerake et son train de glisseurs

On connaît maintenant de méthodes pour passer de la construction d'un puffer à celle d'un navire. Il "suffit" de modifier le puffer de telle sorte qu'il détruise lui-même ses propres traces. L'inverse est également parfois possible, mais ce n'est qu'en 1991 que D. Hickerson réussit à convertir en navire le puffer de Corderman [6].

Chacune des configurations précédentes répond à la question initiale de J. Conway. Sa population s'accroît indéfiniment. Mais la proportion d'espace occupée est de plus en plus faible. Aussi peut-on demander, plus précisément : existe-t-il une population capable de "recouvrir le plan" ? Réponse page suivante.

haut de page

Notes

[1]  Lui-même pensait initialement que c'était impossible.

[2]  par allusion à la fumée que laisse un train à vapeur

[3]  La plus petite configuration indéfiniment croissante actuellement connue n'est composée que de 10 cellules (P. Callahan 1997)

[4]  la plus petite période connue actuellement, construite en 2004 par K. Suhajda à partir d'une population de 8814 cellules

[5]  mais on a bien une vague idée...

[6]  ... qui a pris de l'embonpoint au passage (le puffer, pas son auteur), avec 180 cellules !

haut de page