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.

Der Algorithmus 
Die Ameise bewegt sich in einem unendlichen Quadratgitter aus Feldern, die entweder schwarz oder weiß sein können. In der Ausgangssituation sind alle Felder weiß und die Ameise sitzt auf einem der Felder und schaut in eine bestimmte Richtung (in dieser Darstellung nach unten). Der Übergang zum nächsten Zustand erfolgt nach folgenden Regeln:
 Auf einem weißen Feld drehe 90 Grad nach rechts; auf einem schwarzen Feld drehe 90 Grad nach links.
 Wechsle die Farbe des Feldes (weiß nach schwarz oder schwarz nach weiß).
 Gehe zum nächsten Feld in der aktuellen Blickrichtung.
In den ersten ca. 500 Schritten treten wiederholt symmetrische Muster auf. 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. Ein Feld durchläuft dabei einen Zyklus von zwei oder mehr Feldzuständen (Farben): Bevor die Ameise zum nächsten Feld geht, ändert sie den Zustand des aktuellen Felds zum nächsten im Zyklus. Jedem Zustand ist eine Schwenkrichtung zugeordnet, entweder nach Links oder nach Rechts um 90°.
Die ursprüngliche 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.

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.

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.

Weblinks 

 Erklärung des Prinzips in einem Video
 MathWorld: Erklärung mit Angabe weiterführender Literatur

Ameisenprogramme 
 Simulation im Browser (nach dem Prinzip: L-cell / R-cell)

Einzelnachweise 

Automatentheorie
Theoretische Biologie