Das Lebensspiel und andere Gitterautomaten

Zelluläre Automaten

Der folgende Beitrag ist vor 2021 erschienen. Unsere Redaktion hat seither ein neues Leitbild und redaktionelle Standards. Weitere Informationen finden Sie hier.

Sind es Spiele, die man sich gelegentlich zum Zeitvertreib hervorholt, oder sind es mathematische Systeme, an die sich komplizierte theoretische Fragen knüpfen? In der Tat sind sie beides: die zellulären Automaten, auf die man heute immer wieder stößt, wenn man sich mit grundlegenden Fragen der Physik, Mathematik oder Informatik beschäftigt oder sich für künstliches Leben und künstliche Intelligenz interessiert. Genaugenommen gehören sie zur kybernetisch ausgerichteten Systemtheorie, andererseits sind sie so simpel, daß man sie mit ein paar Spielsteinen auf einem Schachbrett in Funktion setzen kann. John Horton Conway, Mathematiker an der Universität Cambridge und Mitglied der Royal Society, der Erfinder des Lebensspiels, richtete dieses im Gemeinschaftsraum seines Instituts ein. Steven Levy, der Verfasser eines vielbeachteten Buches über Künstliches Leben, berichtet, daß das Spiel auf dem Tisch begann, sich aber bald auf den Fußboden ausbreitete und schließlich den ganzen Raum beanspruchte.

Die Personen, die sich beteiligten, hatten sich allerdings nach strengen Regeln zu richten, die bemerkenswert einfach sind:

  1. 1. Unabhängig von ihrem Zustand wird eine Zelle besetzt, wenn genau drei ihrer unmittelbar angrenzenden Nachbarzellen besetzt sind;
  2. 2. Eine bereits besetzte Zelle bleibt besetzt, wenn zwei ihrer Nachbarzellen besetzt sind;
  3. 3. In allen anderen Fällen ist die Zelle unbesetzt.

Conway selbst war fasziniert von den vielfältigen Möglichkeiten, die dieses Spiel bietet. Je nach den Anfangsbedingungen ergeben sich bestimmte Verhaltensweisen, beispielsweise die Ausbreitung eines Musters oder dessen zyklische Verwandlung. Manche Figuren sind auch zu raschem Verschwinden verurteilt. Spezielles Interesse verdienen solche, die sich selbst reproduzieren und dabei durch das Gitter wandern, denn auf diese Weise ist so etwas wie die Ausbreitung einer Nachricht möglich.

Mit dem Problem, das hinter solchen Versuchen steckt, beschäftigte sich schon viele Jahre früher der aus Ungarn stammende und in Amerika zu Ansehen gekommene John von Neumann. Schon als Dreißigjähriger wurde er in das Institute for Advanced Study in Princeton berufen, eine Art Denkfabrik, in der auch Albert Einstein arbeitete. John von Neumann hatte viele Interessen, unter anderem die Quantenmechanik und die Theorie der Automaten. Von hier aus ergibt sich auch eine Verbindung mit der Spieltherapie, die John von Neumann gemeinsam mit Oskar Morgenstern begründete.

Eine Frage, mit der sich John von Neumann im speziellen auseinandersetzte, bezog sich auf einen "universalen Automaten", der insbesondere imstande sein sollte, sich selbst zu reproduzieren. Zuerst sah er diese Aufgabe recht konkret, und setzte für seine Versuche einen Modellbaukasten ein. Dann aber brachte ihn ein Kollege, der aus Polen stammende Stanislaw Ulam, auf die Idee, den Automaten mehr abstrakt darzustellen, und zwar als Verteilung von Zuständen in den Zellen eines Gitters. Und damit war der zelluläre Automat geboren.

Die Aufgabe, einen universalen Automaten mit der Fähigkeit zur Selbstreproduktion zu konzipieren, erwies sich leider als schwerer, als es sich die Wissenschaftler vorgestellt hatten. Schließlich kam John von Neumann auf eine Struktur aus 200.000 Zellen, die 29 Zustände einnehmen können. Erst nach dem Tod des Wissenschaftlers, der 1957 an Krebs starb, fand man einen Fehler im System, den der Philosoph Arthur Burk eliminieren konnte. Dieser arbeitete an der Universität von Michigan, und er war auch der erste, der Computergrafik einsetzte, um zelluläre Automaten wiederzugeben. Die auf dem Monitor wachsenden Verteilungen waren nicht nur aus theoretischen Gründen interessant, sondern erwiesen sich als Möglichkeit zur Simulation physikalischer Prozesse. Das gilt beispielsweise für die Beschreibung magnetischer Eigenschaften der Materie, oder für Strömungen und Diffusion.

Aber auch ein deutscher Pionier der zellulären Automaten ist zu nennen, und zwar kein anderer als Konrad Zuse, der 1969 mit seinem Buch "Rechnender Raum" an die Öffentlichkeit trat. Ihm ging es um eine Art modellhafter Beschreibung der grundlegenden physikalischen Prozesse. Dabei legte er ein dreidimensionales Gitter zugrunde, dessen Zellen zu bestimmten Zuständen fähig sind und mit den Nachbarzellen in Wechselwirkung stehen. So kann man beispielsweise die Bewegung einer Welle durch schrittweise Aktivierung von Zellen in einem zellulär unterteilten Raum ansehen. Zuse erfuhr erst sp"ter von entsprechenden Gedankeng"ngen seiner englischen und amerikanischen Kollegen. So wurden die zellulären Automaten ebenso wie der Computer zunächst einmal zur Domäne der englischen und amerikanischen Wissenschaftler - allerdings mit recht unterschiedlicher Gewichtung. Die zellulären Automaten blieben eher ein Beschäftigungsfeld für Außenseiter, und als später - wieder im Institute for Advanced Study - der englische Mathematiker Stephen Wolfram die Idee der zellulären Automaten wieder aufgriff, wurde er von seinen Kollegen scheel angesehen.

Einer der wenigen deutschen Wissenschaftler, der sich auf die Spieltheorie und im besonderen auf die zellulären Automaten bezieht, ist der Entwicklungsbiologe und Nobelpreisträger Manfred Eigen. In seinem zusammen mit Ruthild Winkler geschriebenen Buch "Das Spiel" zeigt er Zusammenhänge zwischen biologischen Wachstumsprozessen und der Strukturbildung nach den Regeln der zellularen Automaten auf. Er gibt auch einige neue Spiele an, mit denen sich beispielsweise das Konkurrenzverhalten im Pflanzen- und Tierreich demonstrieren läßt. Im Übrigen wurde eines seiner Spiele zur Basis einer künstlerischen Vorführung: In der Kunsthalle Bielefeld zeigten Gottfried Jäger und Karl Holzhäuser Strukturentwicklungen nach den Eigenschen Regeln anhand von Projektionen und Musik.

Der relativ große Bekanntheitsgrad der zellulären Automaten liegt in der Tatsache, daß sich jeder Besitzer eines Personal Computers damit beschäftigen kann. Auch ohne wissenschaftliche Zielsetzung ist es ein ästhetisches Vergnügen, aufgrund selbstgewählter Anfangsbedingungen die Ausbildung von immer wieder überraschenden Mustern zu verfolgen. Im Übrigen hat sich schon Conway das Interesse der Amateure zunutze gemacht. Er probierte immer wieder neue Grundfiguren aus, um solche mit speziellem Verhalten zu finden, beispielsweise eine solche, die eine Art "Geschosse" in die Umgebung sendet. Da dieses Verfahren recht zeitraubend war, setzte er sich mit Martin Gardner in Verbindung, der als Redakteur für die "Mathematischen Spiele" der Zeitschrift "Scientific American" weithin bekannt war. Die beiden versprachen jenem Leser, der die gesuchte "Gleiter-Kanone" fand, einen Preis von 50 Dollar. Diesen holte sich dann allerdings kein Amateur, sondern ein Fachmann für "Künstliche Intelligenz": R. William Gosper, der am MIT in Boston arbeitete. Die Publikationen von Gardner regten aber viele Leser zu eigenen Versuchen an, wobei es zu durchaus interessanten Ergebnissen kam. Irgendjemand hat ausgerechnet, daß durch solche Aktivitäten in den Arbeitszeiten verschiedener Institute und Firmen Arbeitszeit im Wert von vielen Millionen Dollar verlorenging.

Einige Zeit hindurch waren die zellulären Automaten in diesen Kreisen eine Art Mode, bis sich die Begeisterung - ähnlich wie bei den Fraktalen - irgendwann einmal wieder legte. Dabei sind die Möglichkeiten des Lebensspiels sicher noch nicht erschöpft. Es konnte sogar nachgewiesen werden, daß es ein universaler Automat ist, also ein solcher, der als Modell für sämtliche denkbaren Automaten gelten kann. Es ist allerdings keineswegs nötig, immer nur neue Figuren für das Lebensspiel zu erproben - ebensogut kann man natürlich auch die Regeln ändern und nachsehen, was dann geschieht.