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:
|
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. 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.
- 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.
-
Dreiecksgitter, klassische Regeln, 36 Schritte -
Dreiecksgitter, klassische Regeln, 60.000 Schritte -
Dreiecksgitter, klassische Regeln, 6.000.000 Schritte
Weblinks
Ameisenprogramme
- Simulation im Browser (nach dem Prinzip: L-cell / R-cell)
Einzelnachweise
- ↑ Clemens Hovekamp: Langton Ameise, symmetrische Muster
- ↑ Rudy Rucker: Artificial Life Lab. 5. Juni 1993, abgerufen am 13. Oktober 2018 (englisch).
