Literaturquelle und Bilder: [Ga87]
Kann man eine Maschine bauen, die sich selbst reproduziert? Wenn ja, kann eine praktische Anwendung von Zellautomaten für den Entwurf von Schalfkreisen, die sich selbst reprarieren können, nützlich sein (Roger Banks vermutet das)? Kann man mit künstlichen Leben Turing-Maschinen (benannt nach dem Erfinder, ein britischer Mathematiker namens A. M. Turing) bauen? Betrifft das alles "Game of Life"? Oder wird nur "Leben" simuliert: Geburt, Überleben, Tod, Mutation, Selektion, Evolution? Conway spekuliert, daß dies passiert, wenn eine große Brühe zufällig verteilter Bits am Anfang des Spiels vorliegt. Manche Populationen werden verschwinden, andere sich schädlich oder nützlich entwickeln. Weiters ist wahrscheinlich, denkt Conway, daß sich selbstproduzierende "Tiere" bilden werden.
Dieses Spiel gehört wegen seiner Analogien mit dem Aufstieg, Untergang und der Veränderung einer Gruppe lebender Organismen zu den Simulationsspielen. Simulationsspiele gleichen echten, lebenden Prozessen. Man benötigt einen Spielplan, der aus einem Gitter von Quadraten besteht. Jedes Quadrat bzw. jede Zelle hat acht Nachbarn. Das Spielfeld soll man sich als unendliche Ebene vorstellen. Man spielt nach folgenden Regeln:
Eine lebende
Zelle mit zwei oder drei Nachbarn überlebt die nächste Generation.
Eine
lenbende Zelle mit vier oder mehr Nachbarn stirbt an Überbevölkerung. Hat
eine lebende Zelle nur eine oder keine Nachbarzelle, so stirbt sie an Isolation.
Hat eine
tote Zelle oder besser gesagt ein freies Quadrat genau drei Nachbarn, findet
auf diesem Quarat eine Geburt einer Zelle statt.
Wichtig ist, daß alle Geburten und Sterbefälle gleichzeitig stattfinden. Conway hat diese einfachen Regeln so gewählt, daß folgende wünschenswerte Bedingungen erfüllt werden:
Hat man keine Computer auf dem man das Spiel spielen kann, kann man sich auch mit einem geeigneten Spielbrett und Dame-Steinen behelfen. Man beginnt mit einem Muster aus schwarzen Spielsteinen. Die Zellen, die sterben, markiert man mit einem zweiten schwarzen Stein, den man auf den bereits vorhandenen Stein (die Zelle lebt ja) legt. Auf die leeren Felder, auf denen eine Geburt stattfinden, legt man eine weiße Spielmarke. Man entfernt dann alle toten Steine (zwei Spielmarken übereinander) und die weißen Steine ersetzt man mit schwarzen. Achtung: Geburten und Sterbefälle passieren gleichzeitig!
Es gibt Bevölkerungen, die sterben nach zwei Generation. Andere werden schnell stabil und wieder andere werden zu Oszillatoren (verändern sich immer wieder auf die gleiche Art) oder sogar zu "Flip-Flop' s" (Oszillatoren mit der Periode zwei). Andere Bevölkerungen verändern sich immer wieder.
Sehr interessant ist der von Conway entdeckte Gleiter oder "Federgewicht-Raumschiff", der aus fünf Steinen besteht. Er verschiebt sich leicht und spiegelt sich an einer Diagonalen nach zwei Ticks. Nach weiteren zwei Ticks hat er sich wieder aufgerichtet, ist aber um ein Feld diagonal nach unten gerutscht. Der Gleiter bewegt sich mit ein Viertel Lichtgeschwindigkeit, weil er nach vier Ticks sich reproduziert hat und ein Feld diagonal gewandert ist (Geschwindigkeit = Anzahl der durchwanderten Felder einer reproduzierten Muster / Anzahl der Ticks). "Lichtgeschwindigkeit" deshalb, weil Conway die Geschwindigkeit mit der ein König im Schach in jede Richtung zieht so nennt. Es ist die höchste Geschwindigkeit mit der jede Art von Bewegung auf dem Brett ablaufen kann. Z. B. kann die halbe Lichtgeschwindigkeit nicht mit waagrechten und senkrechten Bewegungen einer endlichen Konstellation im leeren Raum überschritten werden.
Es gibt zusätzlich zum Gleiter noch drei bekannte Raumschiffe: Leichtgewicht-, Mittelgewicht- und Schwergewichts-Raumschiffe. Sie wandern mit halber Lichtgeschwindigkeit waagrecht nach rechts. Sie sprühen Funken, die sofort wieder verschwinden, die sich weiterbewegenden Raumschiffe aber nicht behindern. Übergewichtige Raumschiffe, deren Körperlänge mehr als 6 Steine umfaßt, benötigen zwei oder mehr leichtere Raumschiffe, die verhindern, daß blockierende Funken erzeugt werden.
Conway glaubte Anfangs, daß es kein Muster gibt, daß ins Grenzenlose wächst und schrieb einen Bewerb aus: 50 $ für den, der vor 1970 diese Vermutung beweist oder widerlegt.
1970 wurde von einer Guppe des Artificial Intelligence Projectes beim M.I.T. (Robert April, Michael Beeler, R. William Gosper, Jr., Richard Howell, Rich Schroeppel und Michael Speciner) der Gegenbeweis erbracht. Gosper entdeckte mit Hilfe eines Programms von Speciner eine Gleiterkanone. Eine bestimmte Konstellation wächst nach 40. Ticks zu einer Kanone, die einen Gleiter abschießt. Das passiert alle 30. Ticks wieder. Also ist die Gleiterkanone ein Oszillator mit Periode 30. Die Bevölkerung wächst ins Grenzenlose, da die Gleiter sich fortbewegen und reproduziert.
Daraufhin machte die Gruppe am M.I.T. weitere Entdeckungen. Sie ließen z. B. dreizehn Gleiter zusammenstoßen, wobei dann eine Gleiterkanone entstand. Oder sie verwendeten ein Pentadecathlon, daß einen Gleiter um 180 ° dreht. Mit einem zweiten Pentadecathlon kann man einen Gleiter immer hin und her schicken. Mit einem Pentadecathlon kann auch erreicht werden, daß jeder das Pentadecathlon streifende Gleiter davon "aufgefressen" wird. Eine weitere sehr interessante Konstellation wurde gefunden: Die Gruppe stellte acht Gleiterkanonen so auf, daß die einander kreuzenden Gleiterströme eine Fabrik errichteten, die alle 300 Ticks ein Mittelgewichts-Raumschiff abschießt. Könnte man so Information weiterleiten?
Diese Konstellation wurde von Gosper dann 1971 verbessert. Er stellte vier Gleiterkanonen und ein Penthadecathlon so zusammen, daß eine Fabrik zusammengebaut wird, die alle 60 Ticks leicht- oder mittelgewichtige Raumschiffe abschießt.
Die Bevölkerung des Brüters wächst sehr schnell. Er wurde von der M.I.T.-Gruppe entdeckt. Er besteht aus zehn Dampfzügen (lbewegen sich und lassen eine permanente Rauchspur hinter sich), die sich Richtung Osten bewegen. Die Dampfzüge erzeugen Brüter, die beim Zusammenstoß Gleiterkanonen erzeugen, die augenblicklich aktiv werden und Gleiter abschießen.
Hier ein einfacher Gleiterbrüter von Wainwright:
Gosper fand 1971 auch den "Verschlinger". Das ist eine Konstellation, die aus sieben Bits besteht und andere Muster konsumiert. Die Figur ist sehr stabil, weil sie sich anschließend wieder selber repariert. Es wurden im Laufe der Zeit größere Verschlinger mit seltsamen "Eßgewohnheiten" entdeckt worden.
"Garten Eden", benannt von John W. Tukey, wird ein Muster genannt, daß keinen Vorgänger hat. Diese Konfiguration kann also nicht während eines Spiels entstehen und sich auch nicht reproduzieren. Edward F. Moore hat ein Theorem aufgestellt, aus dem folgt, daß es in Conways Spiel eine solche Konfiguration geben muß.Alvy Ray Smith III von der New York University' x School of Engineering and Science konnte mit Hilfe der Formel von Moore beweisen, daß ein Garten-Eden-Muster in einem Raum mit der Seitenlänge von 10 Milliarden Zellen existiert.
Garten-Eden-Muster von
Roger Banks
1971 wurde dann von Roger Banks ein solches Muster gefunden. Ein weiteres wurde 1974 von einer Gruppe der Universität von Bordeaux gefunden, dessen Leiter J. Harouin-Duparc).
Es gibt noch viele weitere sehr interesante Muster, die hier nicht weiter beschrieben werden. Wichtiger ist es, folgende Frage zu behandeln, die von Martin Gardner 1971 in der Februar-Ausgabe des Scientific American aufgeworfen wurde [Ga87]. Lassen die Regeln des "Game of Life" die Konstruktion eines Universalcomputers zu? Dazu mußte bewiesen werden, daß das "Game of Life" universal ist. Gosper und Conway haben das1971 unabhängig voneinander gemacht. Sie zeigten, wie Gleiter als Impulse zur Simulation einer Turing-Maschine verwendet werden können (siehe Conway' s Buch WinningWays, zweiter Band, verfaßt zusammen mit Elwyn Berlekamp und Richard Guy). D. h., daß es im Prinzip möglich ist, mit sich bewegenden Gleitern Berechnungen durchzuführen. Aber ergibt sich im Zusammenhang mit Turing-Maschinen wieder ein Halteproblem? Es gibt keine Möglichkeit festzustellen, wie und wie lange sich ein Muster im "Game of Life" verändert oder ob es einen stabilen Endzustand erreicht? Und fragt sich Conway 1981 bezüglich Selbstreproduktion von Maschinen nicht selbst in einem Brief an Martin Gardner [Ga87]: "Wenn (frag Gosper) Gleiter zusammenstoßen können, um einen Pentadecathlon zu formen, dann kann ich selbstreproduzierende Maschinen erzeugen, und es ist unentscheidbar, ob eine vorgegebene Maschine selbstreproduzierend ist."
Roll up for the Mystery Tour
the magical Mystery Tour is waiting
to take you away
waiting to take you away.
