Conways Spiel des Lebens

Klicke Zellen an, um dein eigenes Muster zu erschaffen – oder lade ein klassisches Muster – und drücke Play, um zu sehen, wie einfache Regeln komplexes Leben erzeugen.

Rechenbeispiel — Conways Spiel des Lebens

Generation	0
Lebende Zellen	5
Dichte	0.6%
Phase	In Entwicklung
Regel (B3/S23)	n=3⇒Geburt,n∈{2,3}⇒Überleben,sonst⇒Tod

Das sind die Werte, die der Rechner beim Öffnen der Seite anzeigt. Ändere oben eine Eingabe, um sie neu zu berechnen.

Interaktive Simulation wird geladen...

Lektion

Die Theorie — Conways Spiel des Lebens

Das ganze Spiel des Lebens sind zwei Zahlen. B3: eine tote Zelle mit genau drei lebenden Nachbarn wird geboren. S23: eine lebende Zelle mit zwei oder drei Nachbarn überlebt, sonst stirbt sie. Es gibt keine weitere Regel, keinen Zufall und keinen Spieler — du setzt die erste Generation, alles Weitere ist erzwungen. Alles, was das Feld zählt, und jedes Muster in der Liste ist eine Folge dieser beiden Zahlen, gleichzeitig auf jede Zelle angewandt.

Was die einzelnen Symbole bedeuten

n: die Anzahl lebender Zellen unter den acht Nachbarn einer Zelle — vier Kanten, vier Ecken. Jede Entscheidung im Spiel fällt anhand dieser einen ganzen Zahl.
B3: die Geburtsregel. Genau drei: zwei sind zu wenig, vier zu viel, und diese Schärfe ist der Grund, warum Muster klare Ränder haben statt Schlieren.
S23: die Überlebensregel. Eine lebende Zelle mit weniger als zwei Nachbarn stirbt wie vereinsamt, mit mehr als dreien wie überfüllt.
Phase: das eigene Urteil des Feldes darüber, was das Muster tut — Evolving, Still life, Oscillating oder Extinct. Ein Vergleich mit früheren Generationen, keine Vorhersage.

Woher die Formel kommt

Zähle für jede Zelle des Bretts die lebenden unter ihren acht Nachbarn. Auch für die toten Zellen — Geburt wird genauso entschieden wie Überleben, und eine Zelle, die es noch nicht gibt, hat trotzdem Nachbarn.
Wende B3 an. Eine tote Zelle mit n = 3 wird lebendig. Lade den Block und prüfe nach: jede leere Zelle, die ihn berührt, sieht höchstens zwei lebende, also wird neben ihm nie etwas geboren. Genau deshalb bleibt der Block liegen.
Wende S23 an. Eine lebende Zelle mit n = 2 oder n = 3 bleibt. Jede der vier Blockzellen berührt genau drei andere, also überleben alle vier, und der Block bildet sich exakt neu.
Und all das gleichzeitig. Jede Zelle wird gegen dieselbe Momentaufnahme geprüft, dann wird das ganze Brett ersetzt. Aktualisiere stattdessen Zelle für Zelle, und du bekommst ein anderes, falsches Spiel — der bereits geänderte Nachbar würde in die Zelle daneben zurückwirken. Gleichzeitigkeit ist kein Implementierungsdetail, sondern Teil der Regel.

So liest du, was du siehst

Beobachte die Zeile Phase statt des Gitters. Lade den Block, und nach einer Generation steht dort Still life; der Blinker braucht zwei, bis Oscillating erscheint; der Diehard läuft 130 Generationen und zeigt dann Extinct. Lade nun den Gleiter und schrittweise, so lange du magst. Er bleibt für immer Evolving — und er ist das Ordentlichste im Menü, das seine Form alle vier Generationen exakt wiederholt. Der Klassifikator vergleicht das ganze Brett mit früheren Brettern, und das Brett eines Gleiters wiederholt sich nie, weil die Form ein Feld diagonal weitergerückt ist. Ordnung, die wandert, ist für einen Test auf Ordnung, die bleibt, unsichtbar.

Setzt voraus: Ein endliches Brett — und eines, das du nicht ganz kontrollierst: jedes Muster bringt seine eigene Gittergröße mit und überschreibt deine. Die Seite öffnet mit 30×30; wähle Acorn, und es wird 50×50, setze von Hand 70, und das hält, wähle dann Diehard, und es fällt auf 40×40. Conways Regel ist auf einer unbegrenzten Ebene definiert, ein Muster, das hier den Rand erreicht, spielt also nicht mehr ganz dasselbe Spiel.
Versagt, wenn: Die Phase-Zeile kann dir nie sagen, dass ein Muster überleben wird. Lade den Diehard: sieben Zellen, die auf vierundzwanzig anwachsen, über hundert Generationen umherziehen und bei Generation 130 verschwunden sind — der Name ist verdient. Nichts auf dem Bildschirm hat das vor Generation 130 angedeutet, und nichts hätte es gekonnt. Das Spiel des Lebens ist Turing-vollständig, also ist die Frage „stirbt dieses Muster aus?“ das Halteproblem mit anderem Hut, und kein Algorithmus entscheidet sie. Was das Feld beantwortet, ist die entscheidbare Frage — hat sich dieses Brett schon wiederholt? — und es sagt sorgfältig Evolving statt etwas Stärkerem, solange es wartet.

Ein stilles Leben ist nicht „nichts passiert“ — es ist Arithmetik, die in jeder Zelle gleichzeitig aufgeht

Lade das Muster block und zähle selbst nach. Jede seiner vier lebenden Zellen berührt genau drei weitere lebende Zellen, und drei ist sowohl die Geburtszahl als auch eine Überlebenszahl — also lebt jede von ihnen weiter. Gleichzeitig berührt jede leere Zelle rund um den Block höchstens zwei lebende Zellen, und zwei ist nicht drei, also kann nichts geboren werden. Der Block bleibt nicht bestehen, weil ihm nichts geschieht, sondern weil die Regel überall und in jeder Generation ausgewertet wird und die Zählung in alle Richtungen gleichzeitig günstig ausfällt. Brich eine Ecke ab, und dieses Gleichgewicht ist weg.

Ein Spiel ganz ohne Spieler

Conways Life ist ein Nullspieler-Spiel: du setzt die Startzellen, drückst auf Start und greifst danach nie wieder ein. Alles Weitere folgt aus nur zwei Regeln — eine tote Zelle mit genau 3 lebenden Nachbarn wird geboren, und eine lebende Zelle überlebt nur mit 2 oder 3 Nachbarn. Daraus ergeben sich drei Schicksale: Manche Muster erstarren für immer, manche blinken in einer Schleife, und manche (wie der Gleiter) wandern stetig über das Gitter.

Die 50-Dollar-Wette, die Conway verlor

1970 vermutete Conway, dass kein Startmuster unbegrenzt wachsen könne, und bot über Martin Gardners Kolumne im Scientific American 50 Dollar für eine Antwort. Schon wenige Wochen später baute Bill Gospers Gruppe am MIT die Gleiterkanone — ein Muster, das alle 30 Generationen einen neuen Gleiter ausstößt, sodass die Population grenzenlos wächst. Gosper gewann das Geld und widerlegte die Vermutung; die Kanone lässt sich oben als Muster laden.

Aufgabe vollständig gelöst

Fünf lebende Zellen auf einem 30 × 30 Gitter 5 Schritte
Fünf lebende Zellen auf einem 30 × 30-Gitter. Berechnen Sie die vom Panel angezeigte Dichte und ermitteln Sie dann, wie schnell sich der Gleiter bewegt und warum er sich nicht schneller bewegen kann. Dies ist der Zustand Gleiter.

Öffne diese Aufgabe im Tool
1. Die Dichte ist einfach die Anzahl der lebenden Zellen geteilt durch die Gesamtzahl der Zellen, und das Gitter ist quadratisch.
  
  $30\times30=900\ \text{cells},\quad 5\ \text{alive}\ \Longrightarrow\ \frac{5}{900}=0.56\%\to0.6\%$
2. Die Regel in ihrer Gesamtheit. Man beachte, was sie nicht enthält: irgendeinen Begriff von Richtung, Entfernung oder Gedächtnis. Eine Zelle sieht acht Nachbarn und die aktuelle Generation, und das ist alles.
  
  $\text{B3/S23}:\ \text{a dead cell with exactly 3 live neighbours is born; a live cell with 2 or 3 survives}$
3. Verfolgt man den Gleiter über vier Schritte, gleicht er wieder sich selbst, um eine Zelle nach rechts und eine Zelle nach unten versetzt. Zwei dieser Schritte sehen dem Anfang überhaupt nicht ähnlich, weshalb die Periode vier und nicht zwei beträgt.
  
  $g\to g+4:\ \text{the glider returns to its own shape, translated by }(1,1)$
4. Die Geschwindigkeit ist die Versetzung geteilt durch die Periode. Der Nenner der Grenzgeschwindigkeit wird durch die Nachbarschaft bestimmt: Eine Zelle pro Generation ist das Schnellste, wie sich Information bewegen kann.
  
  $v=\frac{1\ \text{cell diagonally}}{4\ \text{generations}}=\frac{c}{4},\ \text{where }c=1\ \text{cell per generation is the causal limit}$
5. Skaliert auf das Spielfeld: Die Durchquerungszeit ist eine Eigenschaft des Musters und des Gitters, nicht der Animationsgeschwindigkeit — diese ändert nur, wie lange man wartet.
  
  $\text{crossing 30 cells}:\ 4\times30=120\ \text{generations}=120\times200\ \mathrm{ms}=24\ \mathrm{s}$
Antwort

c/4, wobei c eine Zelle pro Generation ist. Life hat eine strikte Geschwindigkeitsgrenze, die sich direkt aus der Regel ergibt: Eine Zelle betrachtet stets nur ihre acht Nachbarn, sodass sich kein Einfluss schneller als eine Zelle pro Generation ausbreiten kann, egal welches Muster man baut. Das ist der Kausalkegel, und in der Literatur zu Life wird dies ohne viel Ironie als Lichtgeschwindigkeit bezeichnet. Der Gleiter kehrt nach vier Generationen in seine ursprüngliche Form zurück, um eine Zelle diagonal versetzt, sodass er sich mit einem Viertel der Höchstgeschwindigkeit bewegt — und nichts, was aus B3/S23 konstruiert wurde, hat orthogonal jemals c/2 überschritten. Ein Fünf-Zellen-Muster mit einer Periode und einer Versetzung ist das kleinste Objekt in Life, das sich fortbewegt, und es benötigt 120 Generationen beziehungsweise bei dieser Geschwindigkeitseinstellung 24 Sekunden, um das Spielfeld zu überqueren.

$\text{period }4,\ \text{displacement }(1,1)\ \Longrightarrow\ v=\tfrac{c}{4}$

Quellen (3)

Turing completeness made explicit — a working universal Turing machine built out of Life patterns: P. Rendell, "A Universal Turing Machine in Conway’s Game of Life." 2011 International Conference on High Performance Computing & Simulation, 764–772.
The column that introduced Life to a general audience: Martin Gardner, "Mathematical Games: The fantastic combinations of John Conway's new solitaire game 'life'." Scientific American 223, 120–123, October 1970.
Where Life's universality is worked out: E. R. Berlekamp, J. H. Conway & R. K. Guy, Winning Ways for Your Mathematical Plays, volume 4, 2nd edition. A K Peters, 2004. ISBN 978-1-56881-144-4.

Vom 7-Raven-Room-Team · Anhand veröffentlichter Quellen geprüft. Korrekturen willkommen.