Direkt zum Inhalt
Informatik

Vermehrungsfähige Maschinen

Was sind die wesentlichen Eigenschaften des Lebens, auf einer abstrakten Ebene betrachtet? Aufschlüsse könnte ein mathematisches Modell in Form eines zellulären Automaten geben. Ein solcher ist nun auf einem Computer realisiert worden – 60 Jahre nach dem ersten theoretischen Entwurf.
Selbstreduplikation

Lebende Organismen sind komplizierte Aggregate einfacher Bestandteile. Gemäß allen Theoremen der Wahrscheinlichkeitstheorie oder Thermodynamik sind sie sehr unwahrscheinlich. Der einzige Aspekt, der dieses Wunder erklären oder plausibel machen kann, ist die Tatsache, dass sie sich reproduzieren. Ist erst einmal ein Exemplar zufällig entstanden, so finden die Gesetze der Wahrscheinlichkeitsrechnung keine Anwendung mehr, weil dann viele Exemplare entstehen.

John von Neumann, Theory of Self-Reproducing Automata, 1966

Es ist ein beliebtes Thema der Sciencefiction: Ein Roboter stellt eine perfekte Kopie seiner selbst her, ohne Instruktionen von außen zu benötigen. Seine Interaktion mit der Umwelt beschränkt sich darauf, dass er ihr Materie und Energie entnimmt. Unvermeidlich folgt im Roman das nächste Ereignis: Der neu geschaffene Roboter tut es seinem Erzeuger gleich, und alsbald vermehren sich die Blechwesen wie die Karnickel, die Killerbienen oder die Menschen.

Folgerichtig enden die meisten Romane in der großen Katastrophe. Aber von solchen düsteren Endzeitvisionen war die Aufbruchsstimmung Anfang der 1950er Jahre weit entfernt. Die Erbauer der frühen Computer in den USA begannen, die theoretisch ungeheure Leistungsfähigkeit ihrer Geräte zu erfassen und deren Grenzen auszuloten. Wäre es prinzipiell möglich, einen Roboter so zu programmieren, dass er nach einer Anleitung, die in ihm enthalten ist, sich selbst nachbaut? Und was wären dafür die minimalen Voraussetzungen?

Aus Spektrum der Wissenschaft 05/2012
Aus Spektrum der Wissenschaft 05/2012
Kostenloses Probeheft | Blättern Sie durch die aktuelle Ausgabe und sichern Sie sich Ihr kostenloses Probeheft!

Mit dieser Frage beschäftigte sich vor allem John von Neumann (1903 – 1957), der legendäre amerikanische Mathematiker ungarischer Abstammung, dem wir auch die Architektur der heute verbreiteten Computer verdanken. Sein Freund Stan Ulam (1909 – 1984), den er aus gemeinsamer Arbeit an der Entwicklung der Atombombe kannte, schlug ihm vor, das Problem im Rahmen einer vereinfachten abstrakten Welt zu studieren. Nach von Neumanns Tod führte Arthur W. Burks (1915 – 2008), einer der Entwickler des frühen amerikanischen Elektronenrechners ENIAC, dessen Ansätze fort und veröffentlichte sie 1966 in dem Buch "Theory of Self-Reproducing Automata". Das Werk wurde berühmt und regte eine Vielzahl von Forschungsprojekten an.

Die abstrakte Welt, die Ulam seinem Freund nahegelegt hatte, war die der zellulären Automaten. Diese elementaren Rechner, die ein gedachtes unendliches Schachbrett bevölkern, sind mittlerweile Gegenstand einer eigenen wissenschaftlichen Disziplin im Grenzbereich von Mathematik und Informatik – und in der im Prinzip höchst primitiven Welt kann eine Menge passieren! In der Tat gelang es von Neumann, einen zellulären Automaten mit einer Konfiguration zu finden, die sich selbst repliziert. (In der Fachsprache unterscheidet man die Replikation, die absolut genaue Verdoppelung, von der Reproduktion, bei der die Kinder sich von ihren Eltern unterscheiden dürfen.) Sie ist allerdings aberwitzig kompliziert. Obendrein hat von Neumann sie zwar mathematisch korrekt definiert, aber nicht angegeben, wie sie Zelle für Zelle zu realisieren wäre.

Diese überaus mühsame Detailarbeit haben erst 1995 Renato Nobili an der Università di Padova und Umberto Pesavento an der Princeton University geleistet. Um die Sache zu vereinfachen, veränderten sie von Neumanns Entwurf geringfügig: Ihre Zellen können 32 statt 29 verschiedene Zustände annehmen. Die selbstreplizierende Konfiguration besteht aus 6329 Zellen plus einem 145 315 Zellen langen Band, das vergleichbar dem Erbgut von Lebewesen eine Konstruktionsanweisung zum Ablesen enthält. Ein Fortpflanzungszyklus, das heißt das Duplizieren der Konfiguration einschließlich des Bands, erfordert 63 Milliarden Zeitschritte. Jahrzehntelang hätte die verfügbare Rechenleistung nicht ausgereicht, um die Konstruktion von Nobili und Pesavento in akzeptabler Zeit auf einem Computer nachzuvollziehen; dieser Kraftakt ist erst vor wenigen Jahren gelungen.

Inzwischen ist auch von Neumanns originale Konstruktion mit 29 Zuständen ausgearbeitet und programmiert worden. William R. Buckley, der 2000 seine Masterarbeit über ein Problem in diesem Zusammenhang geschrieben hatte, arbeitete an dem von ihm gegründeten California Evolution Institute die Einzelheiten aus. Die sich selbst replizierende Konfiguration umfasst 18 589 Zellen, das Kodierungsband besteht aus 294 844 Zellen, und eine Verdopplung benötigt 261 Milliarden Schritte. Heute kann jedermann mit Hilfe des kostenfreien Programms Golly auf dem PC in wenigen Viertelstunden dieses bemerkenswerte mathematische Theaterstück verfolgen, das mehr als 50 Jahre unspielbar war. Das gilt sowohl für die Version von Nobili und Pesavento als auch für die von Buckley. Letztere kommt derjenigen von Neumanns näher, ist aber auch heute noch viel langsamer.

Vereinfachte Modelle

Es geht allerdings auch viel einfacher. Christopher Langton hat 1984 eine Konfiguration gefunden, die zu Beginn aus bescheidenen 86 Zellen besteht und sich gleichwohl selbst reproduziert. Diese Entdeckung und weitere, die ihr folgten, lassen von Neumanns komplexe Konstruktion auf den ersten Blick hoffnungslos ungeschickt erscheinen. Erst wenn man sie im Kontext seiner Zeit betrachtet und von Neumanns am lebenden Vorbild orientierte Vorstellungen miteinbezieht, kann man sie als wissenschaftlichen Durchbruch ersten Ranges erkennen und würdigen.

Damit man überhaupt von Selbstreplikation sprechen kann, muss man den Schauplatz des Geschehens festlegen, sprich eine "Welt" mit präzisen "physikalischen Gesetzen". Das kann unsere Welt sein oder aber auch eine vereinfachte, deren Gesetze durch wenige mathematische Regeln eindeutig und erschöpfend beschrieben werden. Unter diesen künstlichen Einfachwelten sind aus mehreren Gründen die zellulären Automaten besonders reizvoll.

Zelluläre Automaten und das Spiel des Lebens
Zelluläre Automaten und das Spiel des Lebens |

Ein zellulärer Automat besteht aus einem – im Prinzip unendlich großen – Schachbrett; auf jedem Feld (jeder "Zelle") sitzt eine kleine Maschine (ein »Automat«). Alle Automaten sind gleich. Ein Automat befindet sich zu jedem Zeitpunkt in einem von endlich vielen, vorab festgelegten Zuständen. Die Zeit verläuft in diskreten Schritten; und zwar hängt der Zustand jedes Automaten zum Zeitpunkt t + 1 nach einer bestimmten Funktion von seinem eigenen Zustand und von dem seiner Nachbarn zum Zeitpunkt t ab. Typischerweise erklärt man zu Nachbarn die acht Felder, die – über Kante oder über Eck – an das aktuelle Feld angrenzen. Andere Nachbarschaftsdefinitionen sind möglich und gehören ebenso wie die Funktion, die den neuen Zustand jedes Automaten aus dem alten errechnet, zu den "Naturgesetzen", die der Schöpfer dieser primitiven Kunstwelt nach seinem Belieben bestimmen kann.

Der meiststudierte zelluläre Automat ist der zum "Spiel des Lebens" ("Game of Life") von John Conway. Seine Zellen haben die zwei Zustände "tot" (weiß) und "lebendig" (blau). Hat eine lebende Zelle zwei oder drei lebende Nachbarn, so bleibt sie am Leben, andernfalls stirbt sie. Hat eine tote Zelle genau drei lebende Nachbarn, so wird sie lebendig, andernfalls bleibt sie tot. Diese einfachen Regeln erzeugen eine überraschend reichhaltige Dynamik. Insbesondere gibt es »Gleiter«, Anordnungen, die diagonal über das Brett wandern und dabei in regelmäßigen Abständen immer wieder dieselbe Gestalt annehmen. In der abgebildeten Folge der Ereignisse prallen zwei Gleiter aufeinander und vernichten sich dabei gegenseitig: Im elften Zeitschritt sind alle Zellen tot.

Erstens sind sie "diskrete Welten": Sowohl Ort als auch Zeit sind keine kontinuierlichen Variablen, sondern nehmen "diskrete" Werte an, das heißt solche, deren Differenz nicht beliebig klein wird. Das macht sie einfach programmierbar, vor allem weil im Gegensatz zur echten Welt die ganze Differenzialrechnung mit ihren begrifflichen und rechnerischen Schwierigkeiten entbehrlich ist. Zweitens sind in einem zellulären Automaten – wie in unserem Universum – alle Wechselwirkungen lokal: Ein Punkt wirkt auf einen anderen, weit entfernten, nicht unmittelbar und schon gar nicht ohne Zeitverzug, sondern stets nur durch Vermittlung dazwischenliegender Punkte. Drittens dürfen die Gesetze, die man zu Grunde legt, extrem einfach sein, was den entsprechenden zellulären Automaten nicht hindert, ein überaus komplexes Verhalten zu zeigen.

Konrad Zuse (1910 – 1995), der Erfinder des ersten programmierbaren Rechners, ging sogar so weit, in seinem "Rechnenden Raum" von 1967 das ganze Universum als einen zellulären Automaten – mit ungeheuer kleinen Zellen – zu interpretieren (Spektrum der Wissenschaft Spezial 3/2007 "Ist das Universum ein Computer?", S. 6).

Hat man sich auf ein Universum – zum Beispiel einen zellulären Automaten – festgelegt, bleibt zu definieren, was genau unter Selbstreplikation zu verstehen ist. Mathematiker neigen dazu, eine solche Definition auf das absolut Unerlässliche zu beschränken, um nicht aus Versehen einen möglicherweise interessanten Fall auszuschließen. Insbesondere soll dadurch nicht schon ein spezielles Verfahren festgelegt werden. Dementsprechend würde man definieren: Selbstreplikation findet statt, wenn ein Objekt, das in Gestalt eines einzigen Exemplars vorliegt, später in mehreren Exemplaren anzutreffen ist.

Diese Bestimmung stellt sich allerdings sehr rasch als unbrauchbar heraus. Sie schließt nämlich Prozesse ein, die bereits unmittelbar durch die Festlegung der Gesetze erzwungen werden. Nehmen wir als Beispiel einen zellulären Automaten namens "Trivial" mit dem folgenden Gesetz:

  • Eine Zelle ist entweder tot oder lebendig.
  • Eine Zelle bleibt im Zeitpunkt t + 1 lebendig, wenn sie dies zur Zeit t war; eine tote Zelle wird zum Leben erweckt, wenn eine ihrer acht Nachbarzellen lebendig ist.

Wenn es zum Zeitpunkt t = 0 im ganzen Universum eine einzige lebende Zelle gibt, dann erhält man nacheinander 9, 16, 25, 36 … Exemplare dieses Urobjekts. Nach der obigen naiven Definition ist das ein Fall von Selbstreplikation. Allerdings ist sie so einfach, dass wir nichts von ihr lernen! Obendrein dürfte man diesen zellulären Automaten auch als sehr grobes Modell unseres Universums nicht zu wörtlich nehmen. Dass aus nichts etwas entsteht, das verhindern im echten Universum bereits die Erhaltungssätze für Materie und Energie. Man könnte zwar im Prinzip einen stehenden Dominostein als "tot", einen umgefallenen als "lebendig" definieren und daraufhin die Kettenreaktion, die man bei den sorgfältig arrangierten Domino-Fernsehshows bewundern kann, als Selbstreplikation bezeichnen – aber das wäre ziemlich albern.

Immerhin könnte der zelluläre Automat Trivial als Modell für die Ausbreitung einer Schimmelpilzkolonie dienen – mit gewissen Verfeinerungen, denn Schimmelpilze pflegen sich nicht in Form eines Quadrats auszubreiten. Das würde allerdings immer noch keinen großen Erkenntnisgewinn bringen.

Schon etwas besser würde sich der Einfachautomat als Modell für den Mechanismus eignen, der dem Rinderwahnsinn zu Grunde liegt. Die krankhaften Prionen namens PrpSc vervielfachen sich, indem sie Prionen mit der unschädlichen Konformation Prpc bei Kontakt in ihresgleichen verwandeln – genau so, wie eine blaue Zelle des Automaten Trivial die sie umgebenden weißen Zellen verändert.

Diese primitive Form der Selbstreplikation funktioniert nur mit sehr einfachen Objekten. Aber selbst größere Einheiten schützen nicht vor Trivialität. Der folgende Extremfall lässt sich in der Robotik einfach realisieren: Ein Roboter namens A-B besteht aus den zwei Teilen A und B, zum Beispiel aus einem Kopf und einem Rumpf. Jedes Teil ist für sich genommen handlungsunfähig. Nehmen wir an, dass A und B, sowie sie einander nahekommen, Anziehungskräfte aufeinander ausüben, zum Beispiel mittels Magneten, und sich daraufhin von selbst zum einem funktionsfähigen A-B zusammenkoppeln.

Unterstellen wir weiter, dass die Teile A und B massenhaft in der Gegend herumliegen. Dann muss man nur noch einen A-B darauf programmieren, dass er ein A und ein B findet und zusammenbringt, und schon vermehren sich die A-B wie die Karnickel.

Fredkins Replicator repliziert einfach alles

Das ist immer noch weit entfernt von der Vermehrungsweise der Lebewesen, aber nicht mehr ganz so abwegig. Dass sich ein Objekt durch Anziehungskräfte automatisch an den richtigen Platz bewegt, kennen wir von der Anlagerung der Atome an einen wachsenden Kristall. Und Viren entstehen dadurch, dass sich ihre Bestandteile mehr oder weniger von selbst zusammenfügen; allerdings hat das "Muttervirus" die Bestandteile nicht aufgesammelt, sondern ihre Herstellung der Wirtszelle "in Auftrag gegeben".

Wenn wir also die Suche nach selbstreplizierenden Maschinen etwas genauer auf das lebende Vorbild ausrichten wollen, sollten wir den Roboter A-B nicht kategorisch ausschließen. Aber unsere naive Definition ist durch einige Einschränkungen zu ergänzen: Das sich selbst replizierende Objekt darf nicht zu einfach sein, und es darf nicht schon dadurch entstehen, dass einige wenige bereits in seiner Umgebung vorhandene komplexe Bestandteile zusammengebracht werden. Interessanterweise ist selbst damit die Selbstreplikation nicht auf die Art und Weise eingeschränkt, welche die Lebewesen praktizieren, weder in der realen Welt noch in der künstlichen.

Betrachten wir zuerst die letztere. Es gibt eine Familie von einfachen zellulären Automaten mit einer sehr überraschenden Eigenschaft, die von Neumann nicht kannte (sonst hätte er sie zweifellos erwähnt): Jede beliebig komplexe Konfiguration, die sich zum Zeitpunkt t = 0 auf dem Schachbrett befindet, erscheint in mehreren Exemplaren wieder, wenn man nur lange genug wartet, eine Weile später in noch mehr Exemplaren, und so weiter.

Der einfachste dieser zellulären Automaten ist der "Replicator" von Ed Fredkin, einem der frühen Computerpioniere und "Digitalphilosophen". Es ist faszinierend, dem Replicator bei seiner Dynamik zuzusehen. Chaos scheint zu herrschen, bis von einem Zeitschritt zum nächsten plötzlich die Ursprungsstruktur makellos und in vielfacher Ausfertigung auf dem Bildschirm erscheint. Aber es ist nicht schwer zu beweisen, dass genau das eintreten muss. Letztlich ist das spektakuläre Phänomen die Konsequenz einer arithmetischen Eigenschaft des Systems, die nichts mit der belebten Welt zu tun hat und von dieser selbstverständlich auch nicht genutzt wird.

Ein überraschend einfacher Vervielfältigungsautomat
Ein überraschend einfacher Vervielfältigungsautomat |

Edward Fredkin, Serafino Amoroso und Gerald Cooper verdanken wir eine erstaunliche Entdeckung: einen zellulären Automaten namens Replicator, der von jeder beliebigen noch so komplexen Struktur perfekte Kopien erzeugt. Die Regeln für diesen Automaten lauten: Eine Zelle ist entweder lebendig (blau) oder tot (weiß). Sie ist im nächsten Zeitschritt genau dann lebendig, wenn im aktuellen unter ihren acht Nachbarzellen eine ungerade Anzahl lebendig ist.

Aus der Ausgangsanordnung (hier eine in Pixel aufgelöste Silhouette der Mona Lisa) wird nach 256 Schritten dasselbe Muster in achtfacher Ausfertigung. Es ist nicht schwer zu beweisen, dass jede Ausgangsanordnung in dieser Weise vervielfältigt wird.

Das Prinzip lässt sich verallgemeinern. An Stelle von zwei darf die Anzahl der Zustände des Automaten eine beliebige Primzahl p sein. Die Regel lautet dann: Man nehme die Summe der Zustände der acht Nachbarzellen zum Zeitpunkt t. Der Zustand jeder Zelle im Zeitpunkt t + 1 ist gleich dieser Summe modulo p, das heißt, man nehme den Rest bei der Division durch p.

Auch die Anzahl der Kopien ist nicht auf acht festgelegt, sondern kann beliebig vorgegeben werden.

Kopierer, die sich selbst kopieren

Nun zur realen Welt. Hier gibt es auch nichtbiologische Formen der Replikation; die geläufigste ist der Fotokopierer. Er dupliziert auch sehr komplexe Dinge, die auf dem Original geschrieben oder gedruckt sind. Es gibt sogar dreidimensionale Kopierer, die Objekte durch Stereolithografie reproduzieren.

Stellen wir uns einen solchen Apparat nach dem Vorbild vieler Sciencefiction-Romane so perfektioniert vor, dass er jedes Objekt Atom für Atom duplizieren kann. Ein Bewohner dieser Zukunftswelt könnte sich dann – unerotisch, aber bequem – dadurch reproduzieren, dass er in einen Kopierer steigt und auf den Startknopf drückt. Selbstverständlich könnte sich ein Kopierer auch selbst vermehren. Ein Extremfall der nichtbiologischen Selbstreproduktion komplexer Strukturen ist die Vielweltentheorie von Hugh Everett (Spektrum der Wissenschaft 4 /2008, S. 24). Zu ihr gehört die Annahme, dass sich das gesamte Universum in jedem Augenblick selbst vervielfältigt und die verschiedenen Exemplare von da an unterschiedliche Entwicklungen durchlaufen.

Auf der Suche nach lebensähnlichen Formen der Selbstreproduktion müssen wir also unsere Definition noch weiter verschärfen. Bekanntlich trägt jede lebende Zelle eine Art Bauanleitung in ihrer DNA. Wenn sich ein lebender Organismus vermehrt oder auch nur eine Zelle sich teilt, werden einerseits Teile dieser Konstruktionsbeschreibung in Proteine übersetzt, die den neuen Organismus bilden. Andererseits wird sie selbst kopiert, damit auch der neue Organismus über die nötigen Informationen zu seiner Replikation verfügt.

Dieser doppelte Mechanismus von Übersetzung und Kopie ist die Existenzgrundlage jedes lebenden Organismus. Folglich sollte ein Schema der Selbstreplikation, das uns helfen könnte, das Leben zu verstehen, nach diesem "genetischen Prinzip" funktionieren.

Das wusste schon von Neumann, und zwar lange bevor die Struktur der DNA entschlüsselt wurde. In der Tat funktionieren seine selbstreplizierenden zellulären Automaten im Original ebenso wie in der Version von Nobili und Pesavento nach dem Prinzip "Maschine plus Band". Dabei entspricht das Band (von dem im Kasten "Der fortpflanzungsfähige Automat" nur ein sehr kleiner Teil dargestellt ist) dem Genom eines Lebewesens.

Der fortpflanzungsfähige Automat
Der fortpflanzungsfähige Automat |

John von Neumann erfand einen zellulären Automaten mit einer selbstreplizierenden Konfiguration, die so komplex ist, dass ihre Aktivität auf den damals verfügbaren Rechnern nicht nachvollziehbar war – von Papier und Bleistift ganz zu schweigen. Das gelang erst 2008 mit einer geringfügigen Abwandlung, die Renato Nobili und Umberto Pesavento 1995 formulierten und die Tim Hutton im Detail programmierte. Eine große Fangemeinde für zelluläre Automaten stellt dieses Programm und viele andere auf der Website golly.sourceforge.net bereit.

In der Version von Nobili und Pesamento besteht die Konfiguration aus zwei Teilen: einer Maschine, welche die Replikation ausführt, und einem Band, das in kodierter Form den Plan der Maschine enthält. Dieses an ein Genom erinnernde Band ist extrem lang und hier nur teilweise abgebildet.

Die Selbstreplikation verläuft in zwei Phasen. Zunächst liest die Maschine das Band und kopiert es an eine Stelle oberhalb des Originals (a, b, c). In einem zweiten Schritt fährt sie mit einer Art beweglichem Arm – der aus Zellen der Maschine besteht – an der Kopie des Bands entlang, interpretiert die darauf verzeichneten Daten und setzt nach deren Anweisung Zelle für Zelle die neue Maschine zusammen (d, e, f). Sowie diese zweite Phase beendet ist, setzt sich die neue Maschine in Gang und produziert ihrerseits eine Kopie ihrer selbst sowie ihres Bands.

Das »Spiel des Lebens« von John Conway, der bestuntersuchte zelluläre Automat überhaupt, verfügt über zahlreiche universelle Eigenschaften. Daraus folgt, dass es auch in dieser künstlichen Welt eine sich selbst replizierende Anfangskonfiguration geben muss. Allerdings ist dieser Existenzbeweis nichtkonstruktiv, gibt also keinen Hinweis, wie diese Konfiguration zu finden wäre. Dies ist bis heute auch noch niemandem gelungen.

Bei der Selbstvermehrung wird zunächst eine Kopie des Bands hergestellt und dann diese abgelesen und in eine zweidimensionale Struktur übersetzt. Der Kopierer kopiert gewissermaßen seinen eigenen Bauplan und konstruiert mit der Kopie als Vorlage ein zweites Exemplar seiner selbst. Damit wird klar, warum sich von Neumann nicht mit einem zellulären Automaten vom Typ Trivial oder Replicator zufriedengeben konnte. Ist es aber möglich, das Prinzip "Maschine plus Band" einfacher zu realisieren als mit von Neumanns gigantischem und extrem langsamem Apparat?

Einfache Automaten mit Erbgut

Ja! Die Entdeckung geht auf das Jahr 1984 zurück und ist Christopher Langton zu verdanken. Der Informatiker, der auch den Begriff "künstliches Leben" prägte, wurde zuerst bekannt durch seine "Ameisen" (Spektrum der Wissenschaft 8 /1995, S. 10, 9 /1995, S. 12 und 10 /1995, S. 10). Diese virtuellen Tierchen krabbeln über ein unendliches Schachbrett und verändern in Abhängigkeit von ihrem eigenen Zustand den Zustand des Felds, auf dem sie gerade stehen. Das Konzept des zellulären Automaten ist so allgemein, dass es auch die Welt von Langtons Ameisen beschreibt. Es ist kaum ein Zufall, dass sein selbstreplizierender Automat ("Langtons Schleife") so wirkt, als würde er von einer Ameise betrieben: Nur an einer Stelle der Struktur findet Aktivität statt, und diese Stelle wandert typischerweise von Zelle zu Zelle.

Langton-Schleifen
Langton-Schleifen | Diese Konfiguration eines zellulären Automaten (a) kann man mit etwas Mühe noch als ein inneres Genom mit einer Außenhülle verstehen, vor allem weil eine einmal entstandene Zelle der Hülle sich im weiteren Verlauf nicht mehr verändert. Im Prinzip bekommt ein schleifenförmiger "Körper" einen Auswuchs, der sich selbst zur Schleife krümmt (b bis f) und vom "Mutterkörper" abschnürt. Beide Schleifen vermehren sich sodann unabhängig voneinander weiter (g, h).

Langtons Schleife besteht anfänglich aus 86 Zellen, angeordnet zu einem Schlauch mit einem "Genom" im Inneren. Aus ihr sprießt ein "Auswuchs"; der wächst in 150 Zeitschritten zu einer zweiten Schleife heran, in deren Innerem sich eine Kopie des Genoms der ersten Schleife befindet. Diese beiden Schleifen erzeugen wieder neue Schleifen, und so weiter. Nach und nach wird die gesamte Ebene mit Kopien der ursprünglichen Schleife bedeckt.

Erstaunlicherweise gibt es selbst in diesem Modell noch Raum für Vereinfachung. So stellte sich der schützende Schlauch als entbehrlich heraus. Nach weiteren Untersuchungen fanden schließlich James A. Reggia und Hui-Hsien Chou von der University of Maryland 1993 eine selbstreplizierende Konfiguration, die aus nur noch sechs Zellen besteht (Spektrum der Wissenschaft 4 /2002, S. 26). Welche von ihnen zählen zum Genom und welche zur Maschine? Diese Frage lässt sich wahrscheinlich nicht sinnvoll beantworten. Es sieht vielmehr so aus, als sei der Automat von Chou und Reggia eine Zwischenstufe in einem allmählichen Übergang vom Automaten Trivial zur Langton-Schleife. Damit wäre unser Versuch gescheitert, durch eine Definition die interessanten von den uninteressanten Formen der Selbstreplikation abzugrenzen.

Aber diesem unbefriedigenden Zustand lässt sich abhelfen. Wir haben bislang etwas missachtet, das in von Neumanns Augen wesentlich war: Das genetische System sollte nicht nur Kopien seiner selbst erzeugen können, sondern durch Veränderung seines Genoms auch andere Strukturen, die ihrerseits wieder zur Selbstreplikation fähig sind oder auch nicht. Das läuft darauf hinaus, ein wesentliches Element der biologischen Evolution in die künstliche Welt einzuführen, nämlich die Mutation. Wie kann das gelingen?

Evolution der Schleifen
Evolution der Schleifen | Langtons Schleifen können außer Kopien ihrer selbst keine anderen Objekte erzeugen, geschweige denn solche, die sich ebenfalls selbst reproduzieren. Das gelingt mit verallgemeinerten Schleifen, deren Genom veränderlich ist. Die Schleife »Evoloop« von Hiroki Sayama bringt Nachkommen von unterschiedlicher Art und Größe hervor, die auch noch miteinander konkurrieren. Wer eine einzige Evoloop-Schleife im Raum des zellulären Automaten aussetzt, kann in der Folge eine Evolution im darwinschen Sinn beobachten! Zunächst vervielfältigen sich die Schleifen so gut wie unverändert. Wird es dann den Nachkommen zu eng, so entstehen durch Kollisionen zwischen den Schleifen Mutationen der Genome, und neuartige Schleifen treten auf. Manche von ihnen sind nicht lebensfähig und verschwinden nach kurzer Zeit wieder. Im Kampf ums Überleben auf engem Raum setzen sich auf die Dauer die kleinen, robusteren Schleifen durch. Die Bilder zeigen vier Momentaufnahmen dieser Dynamik.

Auch dafür hat von Neumann schon die Grundidee geliefert. Er nannte seine fiktive Maschine "Universal Constructor". Gemeint war eine Konfiguration in einem zellulären Automaten, die nicht nur sich selbst herstellen kann, sondern jede beliebige Konfiguration aus einer sehr großen Klasse. Und zwar gibt es zu jeder geforderten Konfiguration C ein Genom G, so dass der Universal Constructor C produziert, wenn er G abliest. Von Neumanns unförmige Maschine kommt dieser Idee zumindest nahe, während Langtons Schleifen zu solch universellen Leistungen nicht im Entferntesten fähig sind.

Unverkennbar hat von Neumann hier seine Ideen aus der Theorie der Computer auf die Welt der konstruierbaren Gegenstände übertragen – auch wenn diese Welt eigentlich wieder nur im Rechner existiert. Es gibt eine große Klasse von Aufgaben, die "berechenbaren Funktionen", die eine Maschine im Prinzip lösen könnte. Ein Computer heißt universell, wenn er alle berechenbaren Funktionen berechnen kann. Der primitivste aller denkbaren Computer, die Turing-Maschine, die aus nichts als einem Magnetband und einem daran entlangwandernden Schreib-/Lesekopf mit etlichen inneren Zuständen besteht, ist bereits universell.

Es ist kein Problem, eine Langton-Ameise zu definieren, die als Turing-Maschine arbeitet; und da man jede Langton-Ameise als einen speziellen zellulären Automaten definieren kann, gibt es zelluläre Automaten, die zugleich universelle Computer sind. Umgekehrt muss ein universeller Computer in Gestalt eines zellulären Automaten nicht unbedingt aus einer Langton-Ameise hergeleitet sein; selbst Conways "Game of Life" (Kasten "Zelluläre Automaten und das Spiel des Lebens" oben) kann mit einer Anfangskonfiguration versehen werden, so dass er diese Eigenschaft besitzt.

Sex im zellulären Automaten

Für von Neumann war also ein "universeller Konstrukteur" ein naheliegendes Analogon zum universellen Computer. Für ein System, das der Selbstreproduktion nach dem biologischen Vorbild fähig sein soll, wäre diese Fähigkeit allerdings zu viel verlangt. Lebende Organismen können nicht aus einem geeigneten Genom jeden beliebigen materiellen Gegenstand entstehen lassen – und haben das zum Leben auch gar nicht nötig. Für einen "lebensnahen" zellulären Automaten muss man ein vernünftiges Ausmaß an Konstruktionsfähigkeit fordern, aber keine Universalität und schon gar nicht die Fähigkeiten eines universellen Computers. Auch von Neumanns riesige Maschine war noch nicht in seinem Sinn universell.

Damit scheinen wir bei einem zufrieden stellenden Begriff von lebensähnlicher Selbstreplikation angelangt. Er ist allerdings weniger scharf definiert, als man hoffen könnte, weil das Ausmaß der geforderten Konstruktionsfähigkeit nur ungenau bestimmt ist. Dass es von Neumann gelang, im Reich der zellulären Automaten ein lebensähnliches System mit der Fähigkeit zur Mutation auszuarbeiten, beweist, dass die Selbstreproduktion, die man in der Welt des Lebens beobachtet, kein "Wunder" ist (siehe das Zitat zu Beginn des Artikels).

Der Nachweis, dass sein Modell des Lebens als materielle Grundlage nichts weiter braucht als eine diskrete, relativ einfache Physik, ist ein großer Fortschritt. Langtons Schleifen sind zwar für von Neumanns Zwecke zu klein und zu unflexibel; gleichwohl haben sie einige Forscher zu Verallgemeinerungen inspiriert, die auf einfachere Versionen der Von-Neumann-Maschine hinauslaufen. So sind die Schleifen, die Gianluca Tempesti 1995 an der École polytechnique fédérale in Lausanne erfand, mit 148 statt 86 Zellen nur geringfügig komplizierter als die von Langton, können aber recht allgemeine Konstruktionen ausführen.

Andere Modelle, wie der Evoloop von Hiroki Sayama, erzeugen eine ganze Familie selbstreproduzierender Schleifen unterschiedlicher Größe und Form, die einander auch noch den Platz streitig machen, mutieren, Erbgut aus verschiedenen Quellen zusammenführen ("Sex") und damit dem darwinschen Kampf ums Dasein schon recht nahekommen (Kasten "Evolution der Schleifen"). Das hätte von Neumann zweifellos gefallen.

Galilei und Newton haben gezeigt, dass die Planeten nicht Gottes ständiger Zuwendung bedürfen, um auf ihren Bahnen zu bleiben; es genügt, wenn sie den physikalischen Gesetzen folgen. Entsprechend hat von Neumann bewiesen, dass das Leben zu seiner Aufrechterhaltung kein immer währendes Wunder braucht. Das genetische Schema "Maschine plus Band" zusammen mit der Möglichkeit der Mutation genügt. Damit widerlegt von Neumanns Arbeit definitiv das vitalistische Argument, das Leben sei zu komplex, um sich auf die Physik reduzieren zu lassen.

17. KW 2012

Dieser Artikel ist enthalten in Spektrum - Die Woche, 17. KW 2012

Lesermeinung

1 Beitrag anzeigen

Wir freuen uns über Ihre Beiträge zu unseren Artikeln und wünschen Ihnen viel Spaß beim Gedankenaustausch auf unseren Seiten! Bitte beachten Sie dabei unsere Kommentarrichtlinien.

Tragen Sie bitte nur Relevantes zum Thema des jeweiligen Artikels vor, und wahren Sie einen respektvollen Umgangston. Die Redaktion behält sich vor, Leserzuschriften nicht zu veröffentlichen und Ihre Kommentare redaktionell zu bearbeiten. Die Leserzuschriften können daher leider nicht immer sofort veröffentlicht werden. Bitte geben Sie einen Namen an und Ihren Zuschriften stets eine aussagekräftige Überschrift, damit bei Onlinediskussionen andere Teilnehmer sich leichter auf Ihre Beiträge beziehen können. Vielen Dank!

  • Quellen

von Neumann, J.: Theory of Self-Reproducing Automata. University of Illinois Press, Urbana 1966

Pesavento, U.: An Implementation of von Neumann’s Self-Reproducing Machine. In: Artificial Life 2, S. 337 – 354, 1995

Reggia, J. A. et al.: Simple Systems that Exhibit Self-Directed Replication. In: Science 259, S. 1282 – 1287, 1993

SciViews