Langton-Schleife
Langton-Schleifen sind in der theoretischen Biologie eine Form des Künstlichen Lebens. Sie wurden 1984 von Christopher Langton konzipiert. Die „Organismen“ mit der Fähigkeit zur Selbstreplikation, die in einem Zellulären Automaten simuliert werden, bestehen aus einer ringförmigen Anordnung von Zellen, die die „genetische Information“ enthalten. Diese Zellen sind von einer schützenden Hülle umgeben, in der sie beständig rotieren. An einer bestimmten Stelle bricht der Zellstrang mit den „Genen“ die Hülle auf, und der Organismus bildet hier einen Arm (quasi ein Pseudopodium) aus, in den eine vollständige Kopie der Gensequenz eintritt. Diese veranlasst den Arm zu wachsen, sich zu einem neuen Ring (dem Tochterring) zu schließen und sich schließlich vom Elternring abzulösen. Danach sind die beiden genetisch identischen Organismen zu abermaliger Replikation bereit.
Geschichte
1947 stellte John von Neumann mit dem Universal Constructor erstmals einen universellen Zellulären Automaten mit der Fähigkeit zur Selbstreplikation vor, der beliebige Muster einschließlich seiner selbst reproduzieren konnte.[1] Dieser Automat war aufgrund seiner Universalität notwendigerweise sehr komplex, 1968 konnte Edgar F. Codd die Zahl der Zellzustände immerhin von 29 auf 8 reduzieren.[2] Christopher Langton schließlich gelang mit seinem Entwurf[3] wiederum eine erhebliche Vereinfachung, indem er bewusst auf die – in biologischen Systemen ohnehin nicht gegebene – Universalität verzichtete und sich auf die Fähigkeit zur Selbstreplikation beschränkte. Seine Schleifen basieren auf einem der einfachsten Elemente in Codds Automaten, dem sog. Periodic Emitter (Periodic Pulser bei von Neumann) – dem für die Replikation im Wesentlichen zuständigen Organ.
Beschreibung
Der von Langton entworfene Zelluläre Automat ist zweidimensional mit Von-Neumann-Nachbarschaft und 8 Zellzuständen. Die initiale Konfiguration besteht aus 86 Zellen (gezählt werden nur die mit einem von 0 verschiedenen Ausgangszustand, s. Bild). Es existieren mehrere hundert Regeln, die die Zustandsänderungen jeder Zelle beim Übergang von einer zur nächsten Generation festlegen.
Initiale Struktur
Die Hülle wird gebildet aus Zellen mit Zustand 2, sie umschließt den ringförmigen Zellstrang mit dem davon abzweigenden Arm aus Zellen vom Zustand 1. Das Genom ist kodiert als eine Folge von Instruktionen auf diesem Ring. Eine Instruktion besteht jeweils aus einer Zelle in einem der Zustände 4, 5, 6 oder 7, gefolgt von einer Zelle vom Zustand 0. Diese Gensequenz rotiert im Gegenuhrzeigersinn in der ringförmigen Hülle.
Replikation und Entwicklung
Trifft eine Instruktion an der Abzweigung des Armes ein, so wird sie repliziert: das Original zirkuliert weiter durch den Ring, die Kopie tritt in den Arm ein. (Im Beispiel rechts hat die Instruktion 07 die Abzweigung erreicht und würde als Nächstes repliziert werden.) Am Ende des Armes steuern die durch die Gensequenz kodierten Instruktionen die Ausstülpung des Pseudopodiums, das Wachstum und Abknicken des Armes, die Ausbildung der Tochterschleife und deren Abtrennung von der Elternschleife. Damit entstehen durch einen der Knospung ähnlichen Vorgang neue Organismen mit identischem Genom.
In Analogie zur Genexpression verglich Langton die Replikation an der Abzweigung des Armes mit der Transkription, die Umsetzung der Instruktionen am Ende des Armes mit der Translation.
Koloniebildung
Ein Pseudopodium kann nicht in den von einer bestehenden Schleife besetzten Raum eindringen. Dies hat zur Folge, dass Organismen, die an mehreren Seiten von anderen Organismen umgeben sind, sich nicht weiter reproduzieren können; sie sterben ab und bilden mit den benachbarten abgestorbenen Organismen – ähnlich einem Korallenstock – eine Kolonie aus einem Gerüst inaktiver Schleifen mit einer dünnen Hülle sich weiter reproduzierender, lebender Organismen.
Sofern nicht unbegrenzter Lebensraum zur Verfügung steht, ist die Größe einer solchen Kolonie begrenzt, sie nähert sich asymptotisch dem Wert , wobei die Größe des Lebensraumes in Zellen angibt.
Quellen
- John von Neumann, The theory of self reproducing automata, A.W. Burks (ED.), Univ. of Illinois Press, Illinois (1966)
- Edgar Frank Codd, Cellular Automata, Academic Press, New York (1968)
- Christopher G. Langton, Self-reproduction in cellular automata, Physica D Nr. 10 (1984), S. 135–144
Weblinks
- Wachstum einer Kolonie in einem begrenzten Lebensraum (nicht-interaktives Applet)
- Verschiedene selbst-replizierende Automaten (interaktives Applet: Langton Loop und evtl. Step auswählen, mit Erklärungen, englisch)
- Zahlreiche animierte Grafiken zu Langton's Loops (englisch)
- A Self-Repairing Multiplexer-Based FPGA Inspired by Biological Processes (PDF, englisch; 339 kB)