Die Langton-Ameise

Das farbliche Muster wurde von einer Langton-Ameise erzeugt. Die Langton-Ameise ist eine Turingmaschine* zur Untersuchung der Funktionsweise von Algorithmen 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 überraschend chaotisch erscheinende als auch regelmäßig erscheinende Zustände annehmen kann.

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 der Darstellung rechts 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ß).

- Schreite ein Feld in der aktuellen Blickrichtung fort.

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

Das rechts dargestellte farbliche Muster beruht auf einer Verallgemeinerung der klassischen Langton-Ameise. Statt nur schwarz oder weiß kann ein Feld acht verschiedene Farben annehmen, wobei jeder Farbe eine der beiden Schwenkrichtungen (90° nach Rechts oder nach Links) zugeordnet ist. Die ursprüngliche Langton-Ameise wird durch die Regel ‚RL‘ beschrieben. Das hier dargestellte Muster aus acht Farben durch die Regel RLLRRLLR für die Farben weiss, schwarz, grün, rot, orange, hellblau, mittelblau, dunkelblau.

Die Ameise startet auf einem Feld in der Mitte und schaut nach oben. Die Farbe des aktuellen Feldes bestimmt, ob die Ameise das Feld nach rechts oder links verlässt. Hat das Feld die erste Farbe, dann bestimmt der erste Buchstabe des Ameisen-Codes die Richtung, bei der zweiten Farbe bestimmt der zweite Buchstabe die Richtung, usw. Nachdem die Ameise in das Nachbarfeld gewandert ist, wird die Farbe des vorigen Feldes erhöht. Sind alle Farben „aufgebraucht“, dann bekommt das Feld wieder die erste Farbe.

* Eine Turingmaschine ist ein wichtiges Rechnermodell der theoretischen Informatik. Es modelliert die Arbeitsweise eines Computers und dient dazu die Berechenbarkeit und Funktionsweise von Algorithmen zu untersuchen. Sie ist benannt nach dem Mathematiker Alan Turing, der sie 1936 einführte.