Langton-Schleife

2 Langton-Schleifen nach der Replikation (Elternschleife links, Tochterschleife rechts)

Langton-Schleifen (engl. Langton's Loops) stellen eine spezielle Form Künstlichen Lebens dar. Sie wurden 1984 von dem theoretischen Biologen Christopher Langton konzipiert, einem der Mitbegründer der Forschungsdisziplin Künstliches Leben.

Die „Organismen“ mit der Fähigkeit zur Selbstreplikation, die in einem Zellulären Automaten simuliert werden, bestehen aus einer ringformigen 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.

Langton-Schleife – initiale Konfiguration

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 links 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 $\left \lfloor \frac{A}{121} \right \rfloor$, wobei A die Größe des Lebensraumes in Zellen angibt.

Siehe auch

• Langtons Ameise
• Game of Life

Quellen

1. ↑ John von Neumann, The theory of self reproducing automata, A.W. Burks (ED.), Univ. of Illinois Press, Illinois (1966)
2. ↑ Edgar Frank Codd, Cellular Automata, Academic Press, New York (1968)
3. ↑ 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)