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 aus einfachen Regeln 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

Der hier dargestellte Algorithmus gibt vor, dass sich eine Ameise ursprünglich auf einem zunächst weißen Raster befindet und in eine beliebige Richtung auf diesem startet. In dieser Darstellung zuerst nach unten. Für die Darstellung des Vorgangs zeigt das nächste Feld (rechts vom Startfeld in der Tabelle), die Ausführung folgender Regeln:

Ist der Rasterpunkt weiß, so färbt sie ihn schwarz und dreht sich um 90 Grad nach rechts.
Ist der Rasterpunkt schwarz, so färbt sie ihn weiß und dreht sich um 90 Grad nach links.

Danach läuft sie auf den nächsten Punkt im Raster in der neuen Blickrichtung. Die Detaildarstellung ist von Bedeutung, da sie die umgangssprachliche Umschreibung eines mathematisch gefassten Algorithmus versucht, dabei dann aber zunächst wie die unbeholfene Darstellung von Profanitäten wirkt.

In den ersten ca. 10.000 Schritten entsteht ein komplexes, chaotisches Muster. Danach bildet sich eine regelmäßige Struktur („Ameisenstraße“), obwohl es wegen der zugrundeliegenden stärksten Regelsetzung alles andere als Unordnung sein dürfte. Der Begriff „Ameisenstraße“ stellt den Zustand des Objekts in Gegensatz zu den ihn bestimmenden Regeln. Das „Greifbare“ geht über in das dynamisch, organisch Unzugreifende. Der Algorithmus gibt symmetrische Regeln vor, jedoch sind die entstehenden Muster asymmetrisch.

Verallgemeinerungen solcher „Ameisen“ (mit beliebiger Überführungsfunktion) sind auch als Turing Turtle bzw. Turmiten bekannt.

Siehe auch

Weblinks

Commons: Langton's ant – Sammlung von Bildern, Videos und Audiodateien

Erklärung des Prinzips in einem Video

"Ameisenprogramme"

http://www.warrobs.com/langtonvslangton/startseite.php Java Applet; Startpositionen festlegbar
http://www.yahuxo.de/ameise/ameise.html Java Applet (nach dem Prinzip: L-cell / R-cell)