Jeu de la vie

Dans le Jeu de la vie de Conway, chaque case x d’une grille infinie est vivante, $s(x) = 1$, ou morte, $s(x) = 0$. Si N(x) compte les cases vivantes parmi les 8 voisines de x, diagonales comprises, la génération suivante est donnée par

C’est la règle B3/S23. Ici, vous pouvez dessiner des motifs, observer leur évolution, revenir aux générations précédentes, prévisualiser la suivante et voir quand il est prouvé qu’un motif s’est stabilisé.

Toutes les cases sont mises à jour au même instant à partir de la même génération précédente. En pause, Génération suivante montre un pas avant de l’effectuer : les cases qui vont naître sont encadrées, celles qui vont mourir sont barrées. Pointer une case révèle ses 8 voisines et le nombre de voisines vivantes. La grille n’a pas de bord et ne se reboucle pas. Un chevron au bord de l’image indique combien de cases vivantes se trouvent au-delà. La courbe du panneau compte les cases vivantes de chaque génération depuis la dernière modification de la grille.

Quelques types d’objets reviennent souvent. Une structure stable ne change jamais, comme le bloc ou la ruche. Un oscillateur retrouve son état, comme le clignotant toutes les 2 générations. Un vaisseau retrouve sa forme ailleurs : après 4 générations, le planeur s’est décalé d’une case sur le côté et d’une vers le bas. Un canon retrouve son état en laissant quelque chose derrière lui à chaque fois ; le canon de Gosper émet un planeur toutes les 30 générations. Les petits motifs qui mettent longtemps à se stabiliser, comme le pentomino R, sont appelés Mathusalems. Puisque l’état suivant d’une case ne dépend que du bloc de 3 × 3 qui l’entoure, aucun effet ne se propage à plus d’une case par génération, un pas diagonal comptant pour une case. C’est la vitesse de la lumière c, et le planeur avance à c/4.

La page n’annonce la stabilisation d’un motif que lorsqu’elle peut la prouver. La preuve repose sur un fait. Notons F le passage d’une génération. Si deux groupes de cases vivantes X et Y sont distants d’au moins 3 cases, un pas diagonal comptant toujours pour une case, alors

car aucun bloc de 3 × 3 n’atteint les deux groupes. Ainsi, dès que les débris restés sur place se répètent seuls et que chaque vaisseau s’éloigne en restant toujours à au moins 3 cases des débris et des autres vaisseaux, plus rien ne peut les perturber. Sur la courbe, une ligne pointillée marque la première génération à partir de laquelle la grille se compose de ces débris et de ces vaisseaux. Si la page ne peut pas le prouver, par exemple pour des vaisseaux sur le point de se heurter ou un canon qui tire encore, elle ne conclut rien sur la stabilisation. Elle n’affirme jamais non plus qu’un motif ne se stabilisera pas.

John Horton Conway a inventé le jeu en 1970, et Martin Gardner l’a rendu célèbre dans Scientific American en octobre de la même année.