Conways Spiel des Lebens

Conways Game of Life zeigt, wie komplexes makroskopisches Verhalten aus deterministischen, lokalisierten, zweidimensionalen zellulären Automaten entsteht. Der Übergangszustand jeder Zelle wird streng durch die Summe ihrer acht unmittelbaren Nachbarn bestimmt. Trotz dieser grundlegenden mathematischen Regeln weist das System Turing-Vollständigkeit auf und ist für universelle Berechnungen geeignet. Es dient als schlüssiger Beweis dafür, dass extreme algorithmische Komplexität weder Absicht noch zentrale Verarbeitung erfordert.

Conways Life ist ein Nullspieler-Spiel: Sie setzen die Startzellen, drücken auf Start und greifen 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.

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.