🐜 Langtons Ameise — Zellularer Automat, der Highways baut

Zwei auf demselben Gitter interagierende Ameisen können je nach Startposition und -ausrichtung eine große Vielfalt an Ergebnissen hervorbringen: Manche Konfigurationen führen dazu, dass beide Ameisen Highways in unterschiedliche Richtungen bilden, andere führen zu komplexen gegenseitigen Störungen, die die Bildung eines Highways verhindern, und manche erzeugen stabile zyklische Muster. Systeme mit mehreren Ameisen sind theoretisch viel schwerer zu analysieren und werden oft rechnerisch untersucht.

Ein Turmit ist eine 2D-Turingmaschine auf einem Gitter: Er besitzt zusätzlich zur Zellfarbe einen internen Zustand (wie der Kopfzustand einer Turingmaschine), und die Regeln legen fest: (neue Zellfarbe, Drehrichtung, neuer interner Zustand). Langtons ursprüngliche Ameise ist der einfachste Turmit mit 1 internem Zustand und 2 Zellfarben. Der Raum der 2-Zustands-2-Farben-Turmiten enthält 2.592 verschiedene Regeln; eine Handvoll erzeugt Highways, manche erzeugen chaotische Muster, und einige sind rechnerisch universell.

Ja. Varianten wurden auf dreieckigen und sechseckigen Gittern, auf Tori (endliche Gitter mit periodischen Randbedingungen) und sogar auf Cayley-Graphen von Gruppen untersucht. Auf einem Torus muss die Ameise irgendwann einen Zustand erneut besuchen und in einen Zyklus eintreten, sodass der Highway oder ein anderer periodischer Attraktor garantiert ist; auf einem unendlichen Gitter bleibt die Konvergenz zum Highway spekulativ.

Regel 110 ist ein 1D-elementarer zellularer Automat, der 2004 von Matthew Cook als Turing-vollständig bewiesen wurde. Die Verbindung zu Langtons Ameise entsteht über Turmiten: Es wurde gezeigt, dass die Turmite-Regel entsprechend „RL" Simulationen von Regel 110 in ihrem Verhalten einbettet. Das ist bedeutsam, weil es die Turing-Vollständigkeit von Turmit-Systemen an ein unabhängig bewiesenes Turing-vollständiges System anbindet, statt sich auf eine direkte Konstruktion zu verlassen.

Für ein unendliches, leeres (ganz weißes) Anfangsgitter wurde beobachtet, dass der Highway in jeder bekannten Simulation konsistent um Schritt 10.000 entsteht. Die Vermutung, dass dies immer geschieht — unabhängig von Gittergröße oder Simulationspräzision — wurde jedoch nie formal bewiesen. Bei nicht-leeren Anfangskonfigurationen kann sich die Ameise möglicherweise nie in einem Highway einpendeln; es hängt empfindlich vom Anfangsmuster der schwarzen Zellen ab.

Langtons Ameise ist ein kanonisches Beispiel für Emergenz: komplexes globales Verhalten (der Highway) entsteht aus lokalen Regeln ohne explizite Kodierung dieses Musters. Sie wird in der Komplexitätstheorie, der Erforschung künstlichen Lebens und der Wissenschaftsphilosophie als Beleg dafür untersucht, dass sich komplexe Ordnung aus trivial einfachen Regeln selbst organisieren kann. Christopher Langton nutzte sie als motivierendes Beispiel bei der Gründung des Programms für künstliches Leben am Santa Fe Institute.