Spiel des Lebens

In Conways Spiel des Lebens ist jedes Feld x eines unendlichen Gitters entweder lebendig, $s(x) = 1$, oder tot, $s(x) = 0$. Bezeichnet N(x) die Zahl der lebenden Felder unter den 8 Nachbarn von x, einschließlich der diagonalen, so lautet die nächste Generation

Das ist die Regel B3/S23. Hier kannst du Muster zeichnen, ihre Entwicklung beobachten, zu früheren Generationen zurückkehren, eine Generation vorausschauen und erkennen, wann ein Muster nachweislich zur Ruhe gekommen ist.

Alle Felder werden gleichzeitig aus derselben vorherigen Generation berechnet. Im pausierten Zustand zeigt Nächste Generation den Schritt, bevor er ausgeführt wird: Felder, die geboren werden, erhalten einen offenen Rahmen; Felder, die sterben, werden durchgestrichen. Zeigst du auf ein Feld, siehst du seine 8 Nachbarn und die Zahl der lebenden darunter. Das Brett hat keinen Rand und ist auch nicht zyklisch verbunden. Ein Winkelpfeil am Bildrand zeigt, wie viele lebende Felder jenseits davon liegen. Die Kurve im Bedienfeld zählt die lebenden Felder jeder Generation seit der letzten Änderung am Brett.

Einige Arten von Objekten tauchen immer wieder auf. Ein Stillleben verändert sich nie, etwa der Block oder der Bienenstock. Ein Oszillator kehrt zu sich selbst zurück, wie der Blinker alle 2 Generationen. Ein Raumschiff nimmt anderswo wieder seine ursprüngliche Form an: Der Gleiter ist nach 4 Generationen ein Feld zur Seite und eines nach unten gewandert. Eine Kanone kehrt zu sich selbst zurück und lässt dabei jedes Mal etwas zurück; die Gosper-Kanone feuert alle 30 Generationen einen Gleiter ab. Kleine Muster, die lange bis zur Beruhigung brauchen, etwa das R-Pentomino, heißen Methusalems. Da der nächste Zustand eines Feldes nur vom umgebenden 3 × 3-Block abhängt, breitet sich kein Einfluss schneller als ein Feld pro Generation aus; ein diagonaler Schritt zählt dabei als ein Feld. Diese Grenze heißt Lichtgeschwindigkeit c. Der Gleiter bewegt sich mit c/4.

Die Seite meldet ein Muster nur dann als beruhigt, wenn sie das beweisen kann. Der Beweis beruht auf einer Tatsache. Sei F der Schritt um eine Generation. Liegen zwei Gruppen lebender Felder X und Y mindestens 3 Felder auseinander, wobei auch ein diagonaler Schritt als ein Feld zählt, dann gilt

denn kein 3 × 3-Block erreicht beide Gruppen. Sobald die zurückbleibenden Reste für sich periodisch wiederkehren und jedes davonfliegende Raumschiff stets mindestens 3 Felder von ihnen und von den anderen Schiffen entfernt bleibt, kann nichts sie mehr stören. Eine gestrichelte Linie in der Kurve markiert die erste Generation, ab der das Brett aus diesen Resten und Schiffen besteht. Kann die Seite das nicht beweisen, etwa bei Schiffen auf Kollisionskurs oder einer weiterfeuernden Kanone, macht sie keine Aussage zur Beruhigung. Sie behauptet auch nie, ein Muster werde nicht zur Ruhe kommen.

John Horton Conway entwickelte das Spiel 1970. Martin Gardner machte es im Oktober desselben Jahres in Scientific American bekannt.