Der Universal Constructor ist eine sich selbst replizierende Struktur innerhalb eines zellularen Automaten , die beide in den 1940er Jahren von John von Neumann erstellt wurden .
Der von Neumann verwendete Zellularautomat hat 29 verschiedene Zustände. Die selbstreplizierende Struktur verwendet diese 29 Zustände, um Drähte und Signale zu simulieren. Ein Datensatz, der durch eine Abfolge von Zellen gebildet wird, codiert eine Reihe von Aktionen, die die Struktur ausführen muss. Mithilfe eines Schreibkopfs kann diese Struktur neue Zellen erstellen, die die Replikation von sich selbst und der Aufzeichnung ermöglichen.
Von Neumanns universeller Konstruktor ist die Demonstration der logischen Möglichkeit der Selbstreplikation. Dies ist jedoch eine äußerst komplexe Struktur, und im Laufe der Zeit wurden eine Reihe einfacherer Strukturen erstellt (insbesondere die Langton-Schleife ).
Der universelle Konstruktor hat jedoch, wie der Name schon sagt, die Eigenschaft der Universalität : Es ist ihm möglich, nicht nur Kopien von sich selbst, sondern auch Varianten zu erstellen.
Die einfachsten selbstreplizierenden Strukturen (insbesondere die Byl-Schleife und die Chou-Reggia-Schleife ) haben keinen separaten Datensatz, da ihr Replikationsalgorithmus in der Struktur selbst enthalten ist und ihre Skalierbarkeit begrenzt ist. Andere Strukturen wie der Evoloop sind skalierbarer.
Das Konzept der Universalität ist nicht auf den universellen Konstruktor beschränkt: Das Spiel des Lebens hat sich als universell erwiesen . Mit diesem einfachen zellularen Automaten ist es daher möglich, einen universellen Konstruktor zu erstellen, der ähnlich wie der von Neumann entworfene funktioniert: Das erste bekannte Beispiel ist der lineare Propagator im Jahr 2013.
Außerdem hat die HighLife- Variante des Spiels des Lebens eine sich selbst replizierende Struktur, den Replikator, der anfänglich nur aus 12 Zellen besteht.
Der universelle Konstruktor wurde 1995, 50 Jahre nach seiner Gründung, erstmals von Umberto Pesavento und Renato Nobili implementiert.
Nobili und Pesavento präsentierten auch eine Erweiterung des zellularen Automaten, die durch Hinzufügen von drei Zuständen einfachere Kreuzungen zwischen den Drähten und die Schaffung einer kompakteren Struktur ermöglichte. Das Problem wird derzeit weiter untersucht.
Obwohl zellulare Automaten im Allgemeinen schnell ausgeführt werden können, hat die enorme Größe, die für die Aufzeichnung erforderlich ist (über 84.000 Zellen in der ursprünglichen Struktur, daher eine Implementierung von mindestens 85.000 Zellen breit erforderlich), den vollständigen Abschluss eines gesamten Replikationszyklus bisher ausgeschlossen. Der universelle Konstruktor bleibt daher von im wesentlichen theoretischem Interesse.