Ameisen auf "Mystery Tour"

Literaturquellen und Bilder: [St95/8], [Ru95/9], [Ru95/10]

Ameisen. Ameisenhügel. Ameisenstraßen. Ameisensäure. Stark wie eine Ameise. Ameisenbär? Künstliche Ameise. Symmetrische Ameise. Ameise baut Autobahn! Nein! - Doch

Eine Ameise bewegt sich durch ein Gitter aus Quadraten nach festen Regeln. Die Quadrate können definierte Farben annehmen. Die Ameise setzt man auf irgendein Quadrat in eine Himmelsrichtung schauend. Die Farbe des Quadrats bestimmt die nächste Aktion der Ameise. Sie dreht sich um 90 ° nach rechts oder links ins Nachbarfeld, wo das Ganze von vorn beginnt. Die Ameise ist natürlich unsichtbar und die Regeln sind Zustandsüberführungsfunktionen, die für jedes Quadrat gleich sind. Diese Ameise ist ein typisches Beispiel für regelbasierte Systeme.

Chris Langton vom Santa-Fe-Institut hat diese Ameise entdeckt. Sie kennt nur die Farben Schwarz und Weiß und bewegt sich nach folgenden Regeln: Tritt sie auf ein weißes Feld, bewegt sie sich nach rechts und färbt das Feld schwarz; tritt sie auf ein schwarzes Feld, bewegt sie sich nach lins und färbt das Feld weiß. Somit hat diese Ameise die Regelkette RL. Hier fällt eine Ähnlichkeit zur Turing-Maschine auf. Und wirklich: Es gibt ameisenähnliche Tiere, Turmiten genannt, mit denen man alle Ameisen simulieren kann [Ru95/10]. Diese Turmiten realisieren eine Turing-Maschine in zwei Raumdimensionen.

Schickt man eine Ameise nun los, egal ob alle Quadrate weiß sind oder ob endlich viele der Quadrate in beliebiger Anordnung schwarz gefärbt sind, beginnt sie nach ca. 10.000 Schritten eine Struktur zu bauen. Diese Struktur wurde von ihrem Entdecker James Propp von Massachusetts Institute of Technology in Cambridge Autobahn genannt. Vorher kehrt sie eine Zeit lang immerwieder zum Mittelpunkt zurück und erzeugt symmetrische Muster, um dann bis zum ca. 10.000 Schritt chaotisch herumzuwuseln.

Wer sagt nun, daß diese Ameise immer eine Autobahn baut, also auch mit unendlich vielen schwarzen Quadraten im Gitter? Niemand. Das konnte nicht einmal für den fall endlich vieler in beliebiger Anordnung schwarz gefärbter Quadrate bewiesen werden. Für den Fall endlich vieler Quadrate konnten "E. G. D. Cohen und X. P. Kong von der Rockefeller-Universität in New York nur beweisen, daß der Weg der Ameise zwangsläufig unbeschränkt ist. Sie überschreitet die Grenzen jedes endlichen Gebietes." Zitat Ian Stewart [St95/8].

Inhaltsverzeichnis

Es gibt natürlich auch Ameisen die mehr als nur zwei Farben kennen. Eine allgemeine Ameise kennt n Farben, die von 0 bis n - 1 nummeriert sind. Tritt sie auf ein Feld der Farbe k so gibt sie ihm die Farbe mit der nächsthöheren Farbe, also die Farbe k + 1. Ein Feld mit der Farbe n - 1 bekommt die Farbe 0. Natürlich muß auch die Richtung beschrieben sein. Die Laufrichtung wird ihr in einer Kette von Symbolen mitgegeben. Die Kette ist von 0 bis n - 1 durchnummeriert. Befindet sich die Ameise auf einem Feld mit der Nummer k, so führt sie Symbol bzw. Regel Nr. k aus. Die Symbole können entweder 0 und 1 sein, oder man schreibt für 0 L und für 1 R (für links und rechts). Langton' s Ameise hat die Regelkette RL. Schreibt man die Regelkette binär und beginnt die Kette mit einer 0, so kann diese weggelassen werden. Also dürfen alle Regelketten nur mit einem R bzw. einer 1 anfangen, was aber nicht heißt das die anderen Ketten vernachlässigt werden. Man braucht nur die 0 und 1 (L und R) vertauschen, dann erhält man die gespiegelte Ameise [Ru95/9]. So erhält jede Ameise ihre Nummer bzw. ihre Regelkette.

Jede Ameise hat nun ein eigenes Verhalten. Gibt es doch solche, die Autobahnen bauen und andere, die dazu neigen bilaterale symmetrische Muster (z. B. RRLL, RLLLLR) zu erzeugen. Natürlich gibt es auch solche, wie z. B. RLL, die irgendeine chaotische Struktur herstellt oder eine (RR ... R) die immer auf einem 2 x 2 Quadrat herumkrabbelt. Eine Variante von Cohen und Kong' s Beweis zeigt, daß Ameisen mit Regeln, die R und L enthält, eine unbeschränkte Bahn erzeugt.

Inhaltsverzeichnis

Beispiele

Autobahn bauende Ameisen
  • RL: Ca. bis zum 500. Schritt kehrt Langton' s Ameise immerwieder zum Mittelpunkt zurück. Bis zum ugf. 10.000. Schritt erzeugt sie ein unstrukturiertes Muster. Dann geht sie zum Autobahnbau über mit Zykluslänge 104. D. h. nach 104 Schritten verlängert sie das Muster um 2 Felder nach links über.
  • RRL: Nach 150 Schritten beginnt sie eine Autobahn zu bauen. Für ein Stück neue Autobahn benötigt sie 18 Schritte.
  • RRLR: Sie beginnt chaotisch. Nach 250.000 Schritten beginnt der Autobahnbau mit einem Zyklus der Länge 388.
    • Bilateral symmetrische Ameisen
  • RRLL: Sie kommt immer wieder nach Hause. Und genau in diesem Moment ist die das erzeugte Muster spiegelsymmetrisch.
  • RLLRRLLLLRRR: Kommt nach 400.316 Schritten nach Hause zurück und erzeugt symmetrisches Muster.
    • Chaotische Ameisen
  • RLL
  • RLLL
    • Sonstige Ameise
  • LL: Bleibt auf einem 2 x 2 Quadrat.

    • Leicht kommt man von den Ameisen auf John Horton Conway' s "Game of Life", indem man einfach komplexere Regeln zuläßt. Und Conway selbst hat bewiesen, daß in seinem Spiel bestimmte Konfigurationen universelle Turing-Maschinen bilden. Es stellt sich dann die Frage: Werden manche Populationen unbeschränkt wachsen [St95/8]? Kann man doch jede Ameisen auch durch Turmiten (zweidimensionale Turing-Maschinen) ersetzen [Ru95/10] und gibt es noch keinen Beweis dafür, daß eine Ameise, ausgehend von einer beliebigen Konfiguration mit endlich vielen schwarzen Zellen eine Autobahn baut [St95/8]. Es gibt nur einen Beweis dafür, daß die Bahn einer Ameise zwangsläufig unbeschränkt ist.

    Inhaltsverzeichnis