Langtons Ameise

Langtons Ameise ist die einfachste Vertreterin einer ganzen Familie von Ameisen. Bei n Farben, nummeriert ab 0 für leere Felder, besteht eine Regel aus einer Zeichenfolge $r = r_0 r_1 \cdots r_{n-1}$ aus R und L, einem Buchstaben pro Farbe. Langtons Ameise verwendet RL. Steht die Ameise auf Feld p und blickt in Richtung d, lautet ein Schritt:

Die Ameise hat kein Gedächtnis und sieht nur die Farbe unter sich. Hier kannst du beobachten, wie sie erst Ordnung, dann ein Gewirr und schließlich eine Straße erzeugt. Du kannst sie rückwärts laufen lassen, Felder auf ihrem Weg einfärben und andere Buchstabenfolgen ausprobieren.

Die Farben sind die Zustände der Regel. Die Ebene hat keinen Rand und wird nicht an den Rändern verbunden. Die Kurve oben im Bedienfeld zählt nach jedem Schritt die gefärbten Felder.

Auf der leeren Ebene mit Blick nach oben beginnt die Ameise mit kleinen, geordneten Mustern. Manche sind unter einer halben Drehung symmetrisch, etwa nach Schritt 473. Danach folgt für ungefähr zehntausend Schritte ein scheinbar zufälliges Gewirr. Ab Schritt 9 977 wiederholt die Ameise schließlich dieselben 104 Bewegungen, wobei jede Runde um (−2, 2) verschoben ist: zwei Felder nach links und zwei nach unten. Sie baut einen diagonalen Streifen, den sogenannten Highway. Alle 104 Schritte kommen genau 12 gefärbte Felder hinzu. Nur die Bewegungen der Ameise und der Streifen unter ihr wiederholen sich. Das Gewirr dahinter bleibt an seinem Platz.

Ein paar Wiederholungen beweisen nichts: In der nächsten Runde könnte die Ameise auf ein gefärbtes Feld treffen und abbiegen. Deshalb verspricht die Seite eine fortgesetzte Straße erst nach einer Prüfung. Nach der letzten Runde müssen die gelesenen Felder, um die Verschiebung der Ameise versetzt, dieselben Farben zeigen, die die ursprünglichen Felder vor der Runde hatten. Auch die Ameise muss wieder in die damalige Richtung blicken. Zudem müssen in jeder späteren Runde die Felder außerhalb des Bereichs der vorherigen Runde jetzt leer sein und dürfen seit der geprüften Runde von keiner Runde besucht worden sein. Dann trifft jede Runde genau das an, was die vorherige antraf, und führt für immer dieselben Bewegungen aus. Die gestrichelte Linie in der Kurve markiert den Beginn der Wiederholung. Liegt ein gefärbtes Feld voraus, kreist die Seite es ein und gibt kein Versprechen ab.

Für die leere Ebene ist die Straße damit bewiesen, durch die Berechnung zusammen mit dieser Prüfung. Bei RL endeten alle bisher ausprobierten Bretter mit endlich vielen gefärbten Feldern in einer Straße. Dass das für jedes solche Brett gilt, hat aber niemand bewiesen.

Jeder Schritt lässt sich rückgängig machen. Die Ameise blickt in die Richtung ihrer letzten Bewegung; das Feld, von dem sie kam, liegt also hinter ihr, und dessen Farbe ist im Zyklus um einen Schritt weitergerückt. Ein Schritt zurück lautet:

Brett und Ameise bestimmen somit den Zustand einen Schritt zuvor. Rückwärts lässt die Ameise nach der Regel zurücklaufen, statt eine Aufzeichnung rückwärts abzuspielen.

Bei mehr Buchstaben rückt jedes besuchte Feld zur nächsten Farbe weiter. Auf der leeren Ebene erzeugen die Regeltasten sehr unterschiedliche Formen: LLRR ein scheinbar symmetrisches Muster, LRRRRRLLR ein fast ausgefülltes Quadrat und RRLLLRLLLRRR ein wachsendes Dreieck. Wie diese drei langfristig enden, ist nicht bekannt. LLRRRLRLRLLR baut dagegen nach ungefähr dreißigtausend Schritten eine Straße.

Chris Langton beschrieb die Ameise 1986 als Beispiel für künstliches Leben.