Ameise (Turingmaschine)

aus Wikipedia, der freien Enzyklopädie
Wechseln zu: Navigation, Suche

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.

AMEIHUND Langtons Ameise.png
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[Bearbeiten]

Die Ameise befindet sich in einem Raster, bestehend aus quadratischen Feldern, die entweder schwarz oder weiß sein können. In der Ausgangssituation sind alle Felder weiß und die Ameise schaut in eine bestimmte Richtung (in dieser Darstellung nach unten). Der Übergang zum nächsten Zustand erfolgt nach folgenden Regeln:

  1. Auf einem weißen Feld drehe 90 Grad nach rechts; auf einem schwarzen Feld drehe 90 Grad nach links.
  2. Wechsle die Farbe des Feldes (weiß nach schwarz oder schwarz nach weiß).
  3. Schreite ein Feld in der aktuellen Blickrichtung fort.

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 Zustand; jeweils diagonal um 2 Felder verschoben.

Das System kann auch als zellulärer Automat betrachtet werden, bei dem eine einzelne aktive Zelle zusätzliche Zustände kennt (die Ausrichtung der Ameise) und bei dem sich in jedem Schritt nur zwei Zellen ändern (Ausgangs- und Zielfeld der Ameise).

Verallgemeinerungen[Bearbeiten]

Mehrfarbige Langton-Ameisen[Bearbeiten]

Greg Turk und Jim Propp untersuchten eine Erweiterung der klassischen Langton-Ameise. Die Ameisen durchlaufen dabei einen Zyklus von Links- und Rechtsbewegungen, der durch eine Regel beschrieben wird, die aus einer endlichen Folge von "L" (Linksbewegung) und "R" (Rechtsbewegung) besteht. Für eine Regel mit n Zeichen 'L' bzw. 'R' werden n verschiedene Farben zu Darstellung verwendet. Die ursprünglichen Langton-Ameisen werden 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 Ameisen-Straße erzeugen.

Turmiten[Bearbeiten]

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]

Andere Gitter[Bearbeiten]

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

Siehe auch[Bearbeiten]

Weblinks[Bearbeiten]

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

"Ameisenprogramme"[Bearbeiten]

Einzelnachweise[Bearbeiten]

  1. Clemens Hovekamp: Langton Ameise, symmetrische Muster
  2. Rudy Rucker, Artificial Life Lab