Von-Neumann-Universalkonstrukteur

John von Neumanns universeller Konstruktor ist eine sich selbst replizierende Maschine in einer zellulären Automatenumgebung . Er wurde in den 1940er Jahren ohne Computer entwickelt. Die grundlegenden Details der Maschine wurden in von Neumanns Buch „ Theorie der sich selbst reproduzierenden Automaten“ veröffentlicht , das 1966 nach Neumanns Tod von Arthur W. Burks fertiggestellt wurde. ^{[ 2 ]} Er gilt als Grundlage für die Automatentheorie , komplexe Systeme und künstliches Leben . ^{[ 3 ] [ 4 ]} Nobelpreisträger Sydney Brenner betrachtete von Neumanns Arbeit über sich selbst reproduzierende Automaten (zusammen mit Turings Arbeit über Rechenmaschinen) auch als zentral für die biologische Theorie , da sie es uns ermöglicht, „unsere Gedanken über Maschinen, sowohl natürliche als auch künstliche, zu strukturieren“. ^{[ 5 ]}

Von Neumanns Ziel, wie er es 1949 in seinen Vorlesungen an der University of Illinois darlegte ^{[ 2 ]} , war die Entwicklung einer Maschine, deren Komplexität sich – ähnlich wie bei biologischen Organismen unter natürlicher Selektion – automatisch steigern kann . Er fragte, welche Komplexitätsschwelle überschritten werden muss, damit Maschinen sich weiterentwickeln können ^{[ 4 ].} Seine Antwort war die Spezifikation einer abstrakten Maschine , die sich nach dem Start selbst repliziert. In seinem Entwurf besteht die selbstreplizierende Maschine aus drei Teilen: einer „Beschreibung“ (einem „Bauplan“ oder Programm) ihrer selbst, einem universellen Konstruktormechanismus, der jede Beschreibung lesen und die darin kodierte Maschine (ohne Beschreibung) konstruieren kann, und einer universellen Kopiermaschine , die Kopien jeder Beschreibung erstellen kann. Nachdem der universelle Konstruktor eine neue, in der Beschreibung kodierte Maschine konstruiert hat, erstellt die Kopiermaschine eine Kopie dieser Beschreibung. Diese Kopie wird an die neue Maschine weitergegeben, wodurch eine funktionierende Replik der ursprünglichen Maschine entsteht, die sich fortwährend reproduzieren kann. Manche Maschinen gehen dabei umgekehrt vor, indem sie die Beschreibung kopieren und anschließend eine Maschine erstellen. Entscheidend ist, dass sich die selbstreproduzierende Maschine durch die Akkumulation von Mutationen der Beschreibung und nicht der Maschine selbst weiterentwickeln kann und dadurch die Fähigkeit erlangt, an Komplexität zuzunehmen. ^{[ 4 ] [ 5 ]}

Um seine Maschine genauer zu definieren, griff von Neumann auf Ulams Konzept des zellulären Automaten zurück – Stanisław Ulam prägte den Begriff „zellulärer Automat“ im Kontext von Neumanns Arbeit zum selbstreproduzierenden Automaten. Der von ihm verwendete Automat besteht aus einem zweidimensionalen Gitter von Zellen, von denen jede zu jedem Zeitpunkt einen von 29 Zuständen annehmen kann. In jedem Zeitschritt aktualisiert jede Zelle ihren Zustand in Abhängigkeit von den Zuständen der umliegenden Zellen im vorherigen Zeitschritt. Die Regeln für diese Aktualisierungen sind für alle Zellen identisch.

Der universelle Konstruktor ist ein bestimmtes Muster von Zellzuständen in diesem zellulären Automaten. Er enthält eine Zellzeile, die als Beschreibung dient (ähnlich dem Turing-Band ) und eine Folge von Anweisungen kodiert, die als „Bauplan“ für die Maschine fungiert. Die Maschine liest diese Anweisungen nacheinander und führt die entsprechenden Aktionen aus. Die Anweisungen weisen die Maschine an, mithilfe ihres „Konstruktionsarms“ (einem weiteren Automaten, der wie ein Betriebssystem funktioniert ^{[ 4 ]} ) eine Kopie der Maschine ohne das Beschreibungsband an einer anderen Stelle im Zellraster zu erstellen. Die Beschreibung kann keine Anweisungen zum Erstellen eines gleich langen Beschreibungsbandes enthalten, genauso wenig wie ein Behälter einen gleich großen Behälter enthalten kann. Daher enthält die Maschine die separate Kopiermaschine, die das Beschreibungsband liest und eine Kopie an die neu erstellte Maschine weitergibt. Der resultierende neue Satz aus universellem Konstruktor und Kopiermaschinen plus Beschreibungsband ist identisch mit dem alten und wird erneut repliziert.

Von Neumanns Entwurf wurde traditionell als Demonstration der logischen Voraussetzungen für die Selbstreplikation von Maschinen verstanden. ^{[ 3 ]} Es ist jedoch klar, dass weitaus einfachere Maschinen zur Selbstreplikation fähig sind. Beispiele hierfür sind triviales kristallähnliches Wachstum , Template-Replikation und Langton-Schleifen . Von Neumann interessierte sich jedoch für etwas Tiefergehendes: Konstruktion, Universalität und Evolution. ^{[ 4 ] [ 5 ]}

Es ist zu beachten, dass die einfacheren selbstreplizierenden CA-Strukturen (insbesondere die Byl-Schleife und die Chou-Reggia-Schleife ) nicht in einer Vielzahl von Formen existieren können und daher nur sehr begrenzt evolvierbar sind . Andere CA-Strukturen wie die Evoloop sind zwar bedingt evolvierbar, unterstützen aber dennoch keine offene Evolution. Üblicherweise enthalten einfache Replikatoren nicht den gesamten Konstruktionsmechanismus; sie sind in gewissem Maße Informationen, die von ihrer Umgebung kopiert werden. Obwohl der Von-Neumann-Entwurf eine logische Konstruktion ist, könnte er prinzipiell als physische Maschine realisiert werden. Tatsächlich kann dieser universelle Konstruktor als abstrakte Simulation eines physikalischen universellen Assemblers betrachtet werden . Die Frage nach dem Einfluss der Umgebung auf die Replikation ist noch nicht vollständig geklärt, da es unterschiedliche Auffassungen von Rohmaterial und dessen Verfügbarkeit gibt.

Von Neumanns entscheidende Erkenntnis besteht darin, dass die Beschreibung der Maschine, die kopiert und über den universellen Kopierer separat an die Nachkommen weitergegeben wird, eine doppelte Funktion erfüllt: Sie ist sowohl aktiver Bestandteil des Konstruktionsmechanismus bei der Reproduktion als auch Ziel eines passiven Kopierprozesses. Diese Rolle übernimmt die Beschreibung (ähnlich Turings Anweisungsband ) in Von Neumanns Kombination aus universellem Konstruktor und universellem Kopierer. ^{[ 4 ]} Die Kombination aus universellem Konstruktor und Kopierer sowie einem Anweisungsband konzeptualisiert und formalisiert i) die Selbstreplikation und ii) die offene Evolution bzw. das in biologischen Organismen beobachtete Wachstum der Komplexität. ^{[ 3 ]}

Diese Erkenntnis ist umso bemerkenswerter, als sie der Entdeckung der DNA-Struktur durch Watson und Crick und der getrennten Translation und Replikation in der Zelle vorausging – obwohl sie dem Avery-MacLeod-McCarty-Experiment folgte , das die DNA als molekularen Träger der genetischen Information in lebenden Organismen identifizierte. ^{[ 6 ]} Das DNA-Molekül wird durch separate Mechanismen verarbeitet, die seine Anweisungen ausführen ( Translation ) und die DNA für neu gebildete Zellen kopieren ( Replikation ). Die Möglichkeit einer offenen Evolution beruht darauf, dass – genau wie in der Natur – Fehler ( Mutationen ) bei der Kopie des genetischen Materials zu lebensfähigen Varianten des Automaten führen können, die sich dann durch natürliche Selektion weiterentwickeln können . ^{[ 4 ]} Wie Brenner es formulierte:

Turing erfand den speicherprogrammierbaren Computer, und von Neumann zeigte, dass die Beschreibung vom universellen Konstruktor getrennt ist. Dies ist nicht trivial. Der Physiker Erwin Schrödinger verwechselte in seinem 1944 erschienenen Buch „Was ist Leben?“ Programm und Konstruktor, indem er Chromosomen als „Architektenplan und Handwerkskunst in einem“ betrachtete. Das ist falsch. Das Code-Skript enthält lediglich eine Beschreibung der ausführenden Funktion, nicht die Funktion selbst. ^{[ 5 ]}

Von Neumanns Ziel, wie er es 1949 in seinen Vorlesungen an der University of Illinois darlegte ^{[ 2 ]} , war die Entwicklung einer Maschine, deren Komplexität sich – ähnlich wie bei biologischen Organismen unter natürlicher Selektion – automatisch steigern könnte . Er fragte, welche Komplexitätsschwelle überschritten werden müsse, damit Maschinen sich weiterentwickeln und komplexer werden könnten. ^{[ 4 ] [ 3 ]} Seine Machbarkeitsstudien zeigten, wie dies logisch möglich ist. Durch die Verwendung einer Architektur, die einen universellen programmierbaren Konstruktor von einem universellen Kopierer trennt, demonstrierte er, wie die Beschreibungen (Bänder) von Maschinen durch Selbstreplikation Mutationen akkumulieren und so komplexere Maschinen hervorbringen können (die Abbildung unten veranschaulicht diese Möglichkeit). Dies ist ein sehr wichtiges Ergebnis, da man zuvor vermutet hätte, dass es eine fundamentale logische Barriere für die Existenz solcher Maschinen gäbe; in diesem Fall wären biologische Organismen, die sich entwickeln und komplexer werden, keine „Maschinen“ im herkömmlichen Sinne. Von Neumanns Erkenntnis bestand darin, das Leben als Turingmaschine zu betrachten, die analog durch einen zustandsbestimmten Maschinenkopf definiert ist, der von einem Speicherband getrennt ist. ^{[ 5 ]}

In der Praxis zeigt die von Neumann verfolgte Implementierung von Automaten, dass sie kaum evolutionäre Dynamik hervorbringt, da die Maschinen zu fragil sind – die überwiegende Mehrheit der Störungen führt zu ihrer Zerstörung. ^{[ 3 ] Daher ist heute das in seinen Vorlesungen in Illinois [ 2 ]} skizzierte konzeptionelle Modell von größerem Interesse, da es zeigt, wie sich eine Maschine prinzipiell entwickeln kann. ^{[ 7 ] [ 4 ]} Diese Erkenntnis ist umso bemerkenswerter, als das Modell der Entdeckung der DNA-Struktur, wie oben beschrieben, vorausging. ^{[ 6 ]} Bemerkenswert ist auch, dass von Neumanns Entwurf davon ausgeht, dass Mutationen hin zu größerer Komplexität in den (Beschreibungen von) Subsystemen stattfinden müssen, die nicht an der Selbstreproduktion selbst beteiligt sind. Dies wird durch den zusätzlichen Automaten D veranschaulicht , den er für alle Funktionen zuständig machte, die nicht direkt mit der Reproduktion zusammenhängen (siehe Abbildung oben mit von Neumanns System selbstreplizierender Automaten mit Evolutionsfähigkeit). Tatsächlich wurden in biologischen Organismen nur sehr geringfügige Variationen des genetischen Codes beobachtet, was von Neumanns Annahme entspricht, dass der universelle Konstruktor ( A ) und der Kopierer ( B ) sich nicht selbst weiterentwickeln und somit die gesamte Evolution (und das Wachstum der Komplexität) dem Automaten D überlassen . ^{[ 4 ]} In seinem unvollendeten Werk betrachtet von Neumann auch kurz Konflikte und Interaktionen zwischen seinen selbstreplizierenden Maschinen, um die Evolution ökologischer und sozialer Interaktionen aus seiner Theorie der selbstreplizierenden Maschinen zu verstehen. ^{[ 2 ] : 147}

In der Automatentheorie ist das Konzept eines universellen Konstruktors aufgrund der Existenz von Garten-Eden-Mustern (Konfigurationen ohne Vorgänger) nicht trivial. Vereinfacht ausgedrückt ist ein universeller Konstruktor jedoch in der Lage, jedes endliche Muster nicht erregter (ruhender) Zellen zu erzeugen.

Arthur Burks und andere erweiterten die Arbeiten von Neumanns und lieferten wesentlich klarere und vollständigere Details zum Aufbau und zur Funktionsweise seines Selbstreplikationssystems. Besonders hervorzuheben ist die Arbeit von J. W. Thatcher, da er den Aufbau stark vereinfachte. Dennoch gelang es ihnen nicht, einen vollständigen, zellenweisen Aufbau einer Konfiguration zu entwickeln, die zur Selbstreplikation fähig gewesen wäre.

Renato Nobili und Umberto Pesavento veröffentlichten 1995, fast fünfzig Jahre nach den Arbeiten von Ursula von Neumann, den ersten vollständig implementierten selbstreproduzierenden zellulären Automaten. ^{[ 1 ] [ 8 ]} Sie verwendeten einen zellulären Automaten mit 32 Zuständen anstelle von Neumanns ursprünglicher Spezifikation mit 29 Zuständen und erweiterten diese, um einfachere Signalübergänge, eine explizite Speicherfunktion und eine kompaktere Bauweise zu ermöglichen. Sie veröffentlichten auch eine Implementierung eines allgemeinen Konstruktors innerhalb des ursprünglichen 29-Zustands-CA, jedoch keinen, der zur vollständigen Replikation fähig ist – die Konfiguration kann weder ihr Band duplizieren noch ihre Nachkommen auslösen; die Konfiguration kann lediglich konstruieren. ^{[ 8 ] [ 9 ]}

Im Jahr 2004 berichteten D. Mange et al. über die Implementierung eines Selbstreplikators, der mit den Entwürfen von von Neumann übereinstimmt. ^{[ 10 ]}

Im Jahr 2007 veröffentlichte Nobili eine 32-Zustands-Implementierung, die Lauflängenkodierung verwendet , um die Größe des Bandes erheblich zu reduzieren. ^{[ 11 ]}

Im Jahr 2008 veröffentlichte William R. Buckley zwei Konfigurationen, die innerhalb des ursprünglichen 29-Zustands-Zellulären Automaten von Neumann Selbstreplikatoren sind. ^{[ 9 ]} Buckley behauptet, dass die Signalüberschneidung innerhalb von 29-Zustands-Zellulären Automaten von Neumann für die Konstruktion von Selbstreplikatoren nicht notwendig ist. ^{[ 9 ]} Buckley weist außerdem darauf hin, dass jeder Replikator im Sinne der Evolution nach der Replikation zu seiner ursprünglichen Konfiguration zurückkehren sollte, um (theoretisch) mehr als eine Kopie erstellen zu können. Der 1995 veröffentlichte Entwurf von Nobili-Pesavento erfüllt diese Anforderung nicht, der Entwurf von Nobili aus dem Jahr 2007 hingegen schon; dasselbe gilt für Buckleys Konfigurationen.

Im Jahr 2009 veröffentlichten Buckley und Golly eine dritte Konfiguration für von-Neumann-Zelluläre Automaten mit 29 Zuständen, die entweder eine ganzheitliche Selbstreplikation oder eine Selbstreplikation durch partielle Konstruktion durchführen können. Diese Konfiguration zeigt außerdem, dass Signalüberschneidungen für die Konstruktion von Selbstreplikatoren innerhalb von von-Neumann-Zellulären Automaten mit 29 Zuständen nicht notwendig sind.

CL Nehaniv schlugen 2002 und Y. Takada et al. 2004 einen universellen Konstruktor vor, der direkt auf einem asynchronen zellulären Automaten implementiert ist , anstatt auf einem synchronen zellulären Automaten. ^{[ 12 ] [ 13 ]}

Wie von Neumann definierte, beinhaltet die universelle Konstruktion ausschließlich die Konstruktion passiver Konfigurationen. Somit stellte das Konzept der universellen Konstruktion nichts weiter als ein literarisches (oder in diesem Fall mathematisches) Hilfsmittel dar. Es erleichterte andere Beweise, etwa dass eine gut konstruierte Maschine zur Selbstreplikation fähig ist, während die universelle Konstruktion selbst lediglich für einen Minimalfall vorausgesetzt wurde. Unter diesem Maßstab ist die universelle Konstruktion trivial. Daher können zwar alle hier angegebenen Konfigurationen jede beliebige passive Konfiguration konstruieren, jedoch keine die von Gorman entwickelte Echtzeit-Kreuzungsorgan. ^{[ 9 ]}

Alle Implementierungen von Neumanns selbstreproduzierender Maschine benötigen erhebliche Computerressourcen. Beispielsweise benötigt die oben gezeigte Nobili-Pesavento-Implementierung mit 32 Zuständen, obwohl der Maschinenkörper nur aus 6.329 nichtleeren Zellen (innerhalb eines Rechtecks ​​der Größe 97x170) besteht, ein 145.315 Zellen langes Band und 63 Milliarden Zeitschritte für die Replikation. Ein Simulator mit 1.000 Zeitschritten pro Sekunde bräuchte über zwei Jahre für die erste Kopie. Als die erste Implementierung 1995 veröffentlicht wurde, hatten die Autoren ihre eigene Maschine noch nicht erfolgreich repliziert. 2008 wurde der Hashlife- Algorithmus jedoch erweitert, um die Regelsätze mit 29 und 32 Zuständen in Golly zu unterstützen . Auf einem modernen Desktop-PC dauert die Replikation nun nur noch wenige Minuten, benötigt aber viel Speicherplatz.

• 
  Beispiel eines Lesearms mit 29 Zuständen.

• Codds zellulärer Automat
• Langtons Schleifen
• Nobili zelluläre Automaten
• Quine , ein Programm, das sich selbst als Ausgabe erzeugt
• Weihnachtsmann-Maschine
• Wireworld
• Conways Spiel des Lebens

• John von Neumanns zellulärer Automat mit 29 Zuständen, implementiert in OpenLaszlo von Don Hopkins