Ameise (Turingmaschine)

Die Ameise ist eine Turingmaschine mit einem zweidimensionalen Speicher und wurde 1986 von Christopher Langton entwickelt. Sie ist ein Beispiel dafür, dass ein deterministisches (das heißt nicht zufallsbedingtes) System mit einfachen Regeln und einfachem Anfangszustand sowohl für den Menschen visuell überraschend ungeordnet erscheinende als auch regelmäßig erscheinende Zustände annehmen kann.

Die ersten Schritte laufen folgendermaßen ab:

Initial: Die Ameise betritt das weiße Feld, das sich in der Tabelle ganz links, ganz oben befindet, in seiner Mitte und weist in ihrer Ausrichtung nach unten;
Schritt 1.1: Die Ameise macht den Rasterpunkt in der Mitte des Rasters schwarz und dreht sich um 90 Grad nach rechts, sie weist vom Betrachterstandpunkt also nach links;
Schritt 1.2: Die Ameise läuft auf den Rasterpunkt links von der Mitte;
Schritt 2.1: Die Ameise macht den Rasterpunkt links von der Mitte schwarz und dreht sich um 90 Grad nach rechts, sie weist also nach oben;
Schritt 2.2: Die Ameise läuft auf den Rasterpunkt links über den Startpunkt.

Der Algorithmus

Die Ameise ist ein Spezialfall einer Turingmaschine, die nur einen Zustand besitzt. Statt auf einem Band bewegt sie sich auf einem unendlichen Quadratgitter aus Feldern, die jeweils schwarz oder weiß sein können, entsprechend einem zweielementigen Bandalphabet. Anfangs sind alle Felder weiß. Die Ameise sitzt auf einem der Felder und schaut in eine orthogonale Richtung (nach oben, unten, links oder rechts; in dieser Darstellung nach unten). Die Ameise führt iterativ einen Schritt nach dem anderen aus, und ein Schritt erfolgt nach folgenden Regeln:

Auf einem weißen Feld dreht sie sich 90 Grad nach rechts, auf einem schwarzen Feld 90 Grad nach links.
Sie wechselt die Farbe des Feldes (weiß nach schwarz oder schwarz nach weiß).
Sie geht zum nächsten Feld in der aktuellen Blickrichtung.

In den ersten ca. 500 Schritten treten wiederholt symmetrische Muster auf.^[1] Danach bildet die Ameise während rund 10.000 Schritten ein komplexes, chaotisches Muster. Schließlich geht sie dazu über, eine regelmäßige Struktur („Ameisenstraße“) zu bauen: Sie gerät alle 104 Schritte in denselben (lokalen) Zustand; jeweils diagonal um 2 Felder verschoben, und baut die Straße bis ins Unendliche weiter.

Verallgemeinerungen

Mehrfarbige Langton-Ameisen

Greg Turk und Jim Propp untersuchten eine Verallgemeinerung der klassischen Langton-Ameise mit beliebig vielen Feldzuständen (zwei oder mehr). Eine Ameise wird durch eine Folge aus den Buchstaben 'L' und 'R' beschrieben: wenn n der Zustand des aktuellen Felds ist, gibt der n-te Buchstabe der Folge die Schwenkrichtung der Ameise an (um 90° nach Links oder nach Rechts). Die Feldzustände werden zyklisch durchlaufen: bevor die Ameise zum nächsten Feld geht, ändert sie den Zustand des aktuellen Felds zum nächsten im Zyklus. Die originale Langton-Ameise wird durch die Regel 'RL' beschrieben.

Einige Regeln erzeugen symmetrische Abbildungen, andere scheinbar vollkommen chaotische, wobei teilweise unbekannt ist, ob diese nach hinreichend vielen Schritten eine Ameisenstraße erzeugen.

Beispiele für mehrfarbige Langton-Ameisen:
RLR: Chaotisches Wachstum.
LLRR: Symmetrisches Wachstum.
LLRRRLRLRLLR: Erzeugt eine Ameisenstraße.
RRLLLRLLLRRR: Erzeugt ein ausgefülltes, wachsendes Dreieck.

Turmiten

Wenn die Ameise zusätzliche Zustände (neben ihrer Orientierung) annehmen kann, so erhält man eine weitere Verallgemeinerung. Für jede Kombination aus Ameisenzustand, Ameisenrichtung und Feldfarbe ist eine Regel für den nächsten Schritt vorgegeben. Aus der Kombination der Namen von Alan Turing und Turmiten-Mitentdecker Greg Turk mit mite, dem Englischen Wort für Milbe, wurde der Begriff turmite (im Englischen gleich ausgesprochen wie termite) gebildet.^[2]

Beispiele für Turmiten:
Spiralförmiges Wachstum.
Semi-chaotisches Wachstum.
Chaotisches Wachstum mit anschließendem Bau einer Ameisenstraße.
Chaotisches Wachstum mit Textur.
Erzeugt eine Fibonacci-Spirale.

Andere Gitter

Statt eines Quadratgitters sind auch Dreiecks-, Sechsecks- und Fünfecksgitter (letztere aus unregelmäßigen kachelbaren Fünfecken) denkbar. Einige Simulationen in Linux-Bildschirmschonern bieten auch diese Option an.