Was hat Pi mit dem Leben zu tun? Auf den ersten Blick nicht viel. Doch tatsächlich hat die Suche nach einer umfassenden Beschreibung des Lebens eine Methode hervorgebracht, um die Kreiszahl zu berechnen – wenn auch auf höchst ineffiziente Art über etliche Generationen simulierter Lebewesen.

Einer Definition von Leben haben sich bereits unzählige Wissenschaftlerinnen und Wissenschaftler gewidmet – jedoch ohne eine vollkommen zufrieden stellende Antwort hervorzubringen. Es gibt zwar ein paar Merkmale, anhand derer die Biologie festmacht, ob etwas lebendig ist. Doch für fast jede der Eigenschaften gibt es ein Gegenbeispiel: einen Organismus, der sie nicht erfüllt.

Auch der Mathematiker John von Neumann ging in den 1940er Jahren der Frage nach, was Leben eigentlich ist. Für ihn waren die Hauptmerkmale eines lebendigen Systems, dass es sich selbst reproduzieren kann und in der Lage ist, alles, was sich algorithmisch berechnen lässt, ausführen zu können. Letzteres bedeutet, dass sich die Funktionsweise eines Computers modellieren lässt. Von Neumann träumte davon, ein solches System durch elektromagnetische Einheiten umzusetzen, die sich in einem Fluid frei bewegen können.

Technisch ließ sich das zum damaligen Zeitpunkt jedoch nicht umsetzen. Mit dem Erscheinen erster Computer war es aber möglich, zumindest ein Modell eines solchen »lebendigen« Systems zu schaffen. Da Rechner damals rar und teuer waren, berechnete man die ersten Simulationen per Hand mit Stift und Papier. Zusammen mit seinem Kollegen Stanislaw Ulam fand von Neumann einen recht komplizierten Weg, ein Modell des Lebens zu entwerfen. Wegen der aufwändigen Berechnungen erforderte es allerdings viel Geduld herauszufinden, wie sich die verschiedenen Generationen primitiver Objekte entwickeln.

Das Leben simulieren

Deshalb erlangte eine andere Umsetzung mehr Aufmerksamkeit: John Horton Conways »Spiel des Lebens« (Englisch: Game of Life). Es besteht aus einer Ebene, die in unzählige quadratische Zellen eingeteilt ist. Diese können »lebendig« (schwarz) oder »tot« (weiß) sein. Am Anfang des Spiels verteilt man lebendige Zellen in der Ebene, die sich nach simplen Regeln weiterentwickeln (sterben oder vermehren).

Conway konnte beweisen, dass es möglich ist, jeden Algorithmus in diesem Spiel auszuführen – man muss dafür nur die passende Startkonfiguration finden. Das Spiel des Lebens kann also einen Computer simulieren. Da diese in der Lage sind, die Kreiszahl Pi zu berechnen, ist es nicht allzu überraschend, dass das Spiel des Lebens ebenfalls die irrationale Zahlenfolge ausgeben kann. Allerdings unterscheidet sich die Programmierung des Spiels deutlich davon, einen Code in herkömmlichen Programmiersprachen zu verfassen – die Aufgabe erweist sich als deutlich abstrakter und komplizierter. Doch das ist nicht der einzige Grund, weshalb der Pi-Algorithmus im Spiel des Lebens noch heute viele Fachleute erstaunt.

Um all das nachzuvollziehen, muss man das Spiel besser verstehen. Conways Modell ist eine spezielle Art von zellulärem Automat. Im einfachsten zweidimensionalen Fall bestehen solche Automaten aus quadratischen Zellen, die ihren Zustand (den man durch eine Farbe oder ein Symbol codieren kann) nach einfachen Regeln ändern. Dadurch entstehen unterschiedliche Muster, die sich zeitlich ändern. Seit von Neumann seine Definition von Leben geäußert hatte, versuchten allerlei technikbegeisterte Personen, ein Modell zu finden, das den Anforderungen genügte. Von Neumann selbst entwarf einen zellulären Automaten, der 29 verschiedene Zustände annehmen kann, wodurch komplexe Muster entstehen und wieder verschwinden.

Das Spiel des Lebens

Conway kam diese Lösung allerdings sehr kompliziert vor. Daher begann er ebenfalls nach einem Automaten zu suchen, der deutlich einfacher wäre, aber trotzdem unvorhersehbare Muster liefern würde – und zwar solche, die eine gewisse Komplexität besaßen und sich nicht immer nur wiederholten oder sogleich verschwanden.

Diese Bedingungen erfüllte schließlich das Spiel des Lebens, das aus nur zwei Zuständen besteht, lebendig und tot. Man verteilt dafür eine bestimmte Anzahl lebendige Zellen in der Ebene und erlegt ihnen drei einfache Regeln auf, nach denen sich ihr Zustand entwickelt:

1. Jede lebendige Zelle mit zwei oder drei benachbarten lebenden Zellen überlebt.
2. Jede tote Zelle mit drei lebendigen Nachbarn wird wiederbelebt.
3. Alle anderen lebenden Zellen sterben. Die toten bleiben hingegen tot.

Conway hatte lange Zeit gegrübelt, um die genauen Regeln zu finden. Sie sollten so einfach wie möglich sein und gleichzeitig eine möglichst große Komplexität hervorrufen. Die oben genannte Mischung schien genau diese Anforderungen zu erfüllen: Sie machen das Verhalten der Zellen unvorhersehbar.

Simulation auf einem Go-Brett

Um sein System zu testen, hatte Conway keinen Computer zur Verfügung. Deshalb nutzte er ein Go-Brett, auf dem er die schwarzen und weißen Steine platzierte und die sich ergebenden Muster studierte. Um das Spiel des Lebens auszuführen, beginnt man mit einer Startkonfiguration an lebenden und toten Zellen. Dann ist man im Prinzip fertig: Es gibt keine Züge mehr, man lässt dem Spiel seinen Lauf.

In jedem Schritt verändert man den Zustand der Zellen gemäß der drei Regeln und erzeugt damit eine neue Generation. So kann man zusehen, wie unerwartete Muster entstehen, sich in der Ebene verteilen und wieder verschwinden. Manche Konfigurationen leben eine Weile, um dann auszusterben. Andere wiederum leben immer weiter und bilden die erstaunlichsten Zusammensetzungen, ohne sich jemals zu wiederholen. Das mathematisch Interessante ist: Man kann nicht allgemein für jede Startkonfiguration vorhersagen, wie sie sich verhalten wird.

Es mag unglaublich erscheinen, aber der einfache Satz an drei Regeln genügt, um jede noch so komplizierte Berechnung auszuführen. Allerdings kann das unter Umständen sehr lange dauern und Unmengen an Speicherplatz erfordern. Aber die größte Schwierigkeit besteht darin, die passende Anfangskonfiguration zu finden, welche die gewünschten Ergebnisse einer Berechnung nach mehreren Generationen erzeugt.

Hobbyspieler auf der Jagd nach spannenden Umsetzungen

Seit der Vorstellung des Spiels in »Scientific American« im Jahr 1970 haben sich etliche Personen daran ausgetobt, von Wissenschaftlern über Programmierern bis hin zu begeisterten Laien. Conway selbst hat sich ebenfalls sehr intensiv mit dem Programm beschäftigt und einige wichtige Erkenntnisse gesammelt. Eines seiner Ziele war es aber, eine Anfangskonfiguration zu finden, mit der sich die Zahl Pi berechnen lässt. Da man jeden Algorithmus durch das Spiel des Lebens ausführen kann, wusste er, dass es auf jeden Fall eine Umsetzung gibt. Finden konnte er sie jedoch nicht.

Um zu verstehen, wie man eine Berechnung im Spiel des Lebens umsetzt, muss man die Funktionsweise eines Computers kennen. Dafür braucht man zunächst Informationseinheiten, wie Einsen und Nullen. Während ein Computer diese durch Spannungen codiert, kann man im Spiel des Lebens bestimmte Strukturen, so genannte Glider, nutzen, die sich von Generation zu Generation quer über die Felder bewegen wie kleine Ameisen. Wenn ein Glider in einer ausgewählten Zelle ankommt, wertet man das also als eine Eins, wenn nichts ankommt, dann als Null.

Computer verarbeiten die binären Signale über drei Logikgatter (AND, OR, NOT). Diese lassen sich ebenfalls über bekannte Strukturen im Spiel des Lebens realisieren. Für das NOT-Gatter gibt es beispielsweise ein Muster, das einen einkommenden Glider auslöscht, aber dafür aus dem Nichts einen Glider erzeugen kann. Kennt man die Strukturen, um die drei Gatter umzusetzen, braucht man noch einen Speicher, der die Ergebnisse sichert. Glücklicherweise lassen sich auch dafür die passenden Konfigurationen aus lebenden und toten Zellen bestimmen. Damit hat man alle Bauteile, die man braucht, um die Funktionsweise eines Computers zu simulieren.

Im Frühjahr des Jahres 2000 gelang es dem Informatiker Paul Rendell, erstmals einen vollständigen Computer im Spiel des Lebens in Form einer Turingmaschine umzusetzen. Diese braucht 11 040 Generationen, um einen Zyklus zu durchlaufen. Andere Nutzerinnen und Nutzer fanden daraufhin weitere Umsetzungen, die teilweise leistungsfähiger und effizienter waren – also weniger Generationen brauchten, um Ergebnisse zu liefern.

Zehn Jahre später entwickelte der damalige Teenager Adam P. Goucher eine Möglichkeit, im Spiel des Lebens die Kreiszahl Pi zu berechnen. Und nicht nur das: Das Spiel liefert nicht einfach bloß einen Satz »Einsen« und »Nullen« (die im Spiel keine Zahlen sind, sondern Signale in Form von Feldkonfigurationen), welche die Zahl auf binäre Weise darstellen. Stattdessen erscheint auf dem riesigen Feld in der rechten oberen Ecke eine Diagonale, auf der die Kreiszahl Nachkommastelle für Nachkommastelle in herkömmlicher Dezimalschreibweise dargestellt ist.

Dafür braucht man jedoch jede Menge Geduld. Nach 63 850 210 955 854 Generationen sind erst 12 Nachkommastellen von Pi aufgelöst. Um diese beeindruckende Leistung zu schaffen, nutzte Goucher einen so genannten Tröpfelalgorithmus, der die Dezimalstellen von irrationalen Zahlen nach und nach – tröpfchenweise – kalkuliert. Diese Methode ist zwar nicht die effektivste, doch sie braucht wenig Speicherplatz, was für das Spiel des Lebens vorteilhaft ist.

Anschließend musste er den Tröpfelalgorithmus im Spiel des Lebens umsetzen. Das ist komplexer, als es klingt. Es ähnelt den Aufgaben erster Programmierer, als es noch keine Kompilierer gab, die lesbare Sprachen wie Python oder C++ in extrem komplizierten Maschinencode umwandeln. Goucher musste also genau verstehen, wie die Bauteile des Computers arbeiten – oder in seinem Fall die einzelnen Strukturen im Spiel des Lebens. Nur so lässt sich die passende Startkonfiguration finden.

Anschließend kann man das Programm starten, damit sich jede Zelle nach den drei einfachen Regeln entwickelt. Und dann heißt es: warten. Und zwar lange. Einen entscheidenden Nachteil hat Gouchers Implementierung nämlich: Möchte man damit doppelt so viele Ziffern von Pi darstellen, also 26, wird es nicht doppelt so lange dauern, sondern die Zeit wächst um ein 64-Faches an!

Eine ideale Berechnungsform stellt das Spiel des Lebens also nicht dar, wenn man die Kreiszahl Pi bestimmen möchte. Dafür ist der Weg dahin umso erstaunlicher: Wer hätte gedacht, dass aus der Frage, was das Leben ist, ein Algorithmus für Pi entsteht?