Langton-Ameisen
Inhalt dieser Seite
Was sind Langton-Ameisen?
Ameise im weißen Feld
Das Programm "ants95"
Futter für die Ameise 
Zwei Ameisen 
Weitere Konstellationen 
Langton-Ameisen im Internet
.
Zur Hauptseite    "Mathematische Basteleien"

Was sind Langton-Ameisen?
Das sind unsichtbare Lebewesen, die sich auf einem quadratischen Gitter aus weißen oder schwarzen Feldern bewegen. Treffen sie auf ein weißes Feld, färben sie es schwarz. Treffen sie auf ein schwarzes Feld, färben sie es weiß.
Sie bewegen sich von Quadrat zu Quadrat, aber nie geradeaus, sondern sie drehen sich bei jedem Schritt um 90°, mal nach links und mal nach rechts. Ist das nächste Feld weiß, so drehen sie sich entgegen dem Uhrzeigersinn (oder nach links) weiter. Ist das Feld  schwarz, drehen sie sich im Uhrzeigersinn (oder nach rechts) weiter.

Das folgende Muster wurde von Langton-Ameisen erzeugt. 

Die Ameisen sind keine reine Spielerei. Sie haben einen wissenschaftlichen Hintergrund. Sie zählen wie zum Beispiel die Lebewesen des "Game of  Life" zu den zellulären Automaten. 
Die Regeln sind erstaunlich einfach. Sie werden Chris Langton vom Santa Fé Institut zugeschrieben. Es gibt inzwischen viele Untersuchungen und Weiterentwicklungen. Ich verweise auf meine Linkliste unten. 

Ich beschränke mich auf dieser Seite auf die Grundregel "LR".

Bekannt wurden sie durch einen Artikel von Ian Stewart in der Zeitschrift Scientific American im Juli 1994. Die deutsche Ausgabe Spektrum der Wissenschaft veröffentlichte eine Übersetzung im August 1995. Beide Artikel sind im Internet verfügbar.


Ameise im weißen Feld top
Der einfachste Fall ist die Bewegung einer Ameise in einem quadratischen Gitter mit nur weißen Feldern. Hier sind die ersten zehn Schritte einer Ameise.

(0) Die an sich unsichtbare Ameise sitzt in einem Feld und bewegt sich zum Beispiel nach Norden. 
(1) Sie findet das nächste Feld weiß vor, färbt es schwarz und dreht sich in Pfeilrichtung. Das ist die Richtung nach links entgegen dem Uhrzeigersinn.
(2) Sie erreicht das nächste Feld, färbt es schwarz und dreht sich in Pfeilrichtung.
(3) (4) Weiter entsteht in den nächsten beiden Schritten ein schwarzes 2x2-Quadrat.
(5) Die Ameise erreicht im fünften Schritt das schwarze Feld, das sie in Schritt 1 gefärbt hatte. Sie färbt es weiß und bewegt sich jetzt aber nach rechts in Richtung des Uhrzeigersinns.
Mit entsprechenden Überlegungen kann man die nächsten Schritte nachvollziehen. 

Je weiter die Ameise fortschreitet, desto ausgedehnter wird das chaotische Muster um den Startpunkt herum. 
Nach etwa 10 000 Schritten passiert etwas Unerwartetes: Sie hinterlässt ein geordnetes Muster, das sich nach unten rechts ohne Ende ausdehnt. Die Ameise baut eine "Autobahn" aus sich wiederholenden Streifen. Jeder Streifen wird in 104 Schritten gebaut und enthält drei schwarze Tetrominos.
Zur Orientierung: Das rote Feld ist das Quadrat, das die Ameise zu Beginn färbt. Es ist an sich auch schwarz. 


In Schritt 368 bildete sich eine bemerkenswerte punktsymmetrische Figur.

Das Programm "ants95"  top
Will man die Bewegung von Langton-Ameisen studieren, so sollte man den Computer einsetzen. Dazu muss man entweder ein Programm schreiben oder man verwendet eins aus dem Internet. Ich bin auf das in Visual Basic 3 geschriebene Programm "ants95" von Edward Richards gestoßen. Man kann es als zip-Datei (309 kByte) herunterladen (URL unten). 
Die meisten Bilder auf dieser Seite stammen von diesem Programm. Phasen der Bewegung wurden mit einem Screenshot festgehalten. Sie sind aber nur ein fader Abklatsch der Bilder voller Dynamik, die das Programm erzeugt. 

Nach dem Start des Programms wird eine Ameise automatisch von einer zufällig gewählten Stelle aus in Bewegung gesetzt. Ich bevorzuge die Einstellung Background/White und Manually Position Ants. Setzt man eine Ameise mit einem Mausklick in die Mitte des Bildschirms, so muss man sich darüber im Klaren sein, dass die Ameise dann schon einen Schritt durchgeführt hat. Sie hat ein Feld geschwärzt. Sie konnte aus vier Himmelsrichtungen kommen:

0-West bedeutet, dass sich die Ameise nach dem Start in Richtung Westen bewegt. Leider hat man es in diesem Programm nicht in der Hand die Himmelsrichtung zu bestimmen. Sie wird beim Mausklick zufällig gewählt. Man kann sie über View/View Starting Positions erfahren und dann mit dem Programm mit View/Repeat List fortfahren.


Futter für die Ameise top
Man gibt als Variation keine weiße Ebene wie oben vor, sondern in ihr ein schwarzes Feld. Es kann als "Futter" bezeichnet werden. Im Folgenden wird untersucht, was passiert, wenn die Ameise ein Feld links des schwarzen Feldes auch schwarz färbt. Es gibt vier Fälle, da die Ameise aus vier Richtungen kommen kann. 

Eine 0-West-Ameise lässt sich nicht beeinflussen, wohl aber die anderen Ameisen. Am Ende steht immer die Autobahn. 

Viele schwarze Felder beeinflussen den Weg der Ameise stärker. Das zeigt das Beispiel eines Quadrates mit der Seitenlänge 25 als Futter. Eine1-North-Ameise färbt im ersten Schritt die obere linke Ecke (hier rot) und setzt sich in Bewegung.
Das ist überraschend: Die Ameise läuft auf den Seiten des Quadrates hin und her, löst sie auf und baut parallel dazu neue Strecken auf. Nach etwa 5500 Schritten wird die Autobahn gebaut. Das gelbe Quadrat zeigt zum Vergleich das Ausgangsquadrat.

Zwei Ameisen    top
Was passiert, wenn zwei Ameisen gleichzeitig in derselben Ebene starten?
Der einfachste Fall ist, wenn die beiden Ameisen in einer weißen Ebene im ersten Schritt zwei nebeneinanderliegende Felder schwärzen. Jede der beiden Ameisen kann sich in die vier Himmelsrichtungen 0-West, 1-North, 2-East und 3-South bewegen. Es gibt 16 Fälle. 
Die Paare werden durch 00, 10, ... , 23, 33 gekennzeichnet:

Die linke Ameise färbt die Felder schwarz, die rechte dunkelblau. So kann man erkennen, welche Ameise welches Feld färbt. 

Es gibt die Fälle (I), (II) und (III).
(I) Acht Ameisenpaare benehmen sich so, wie man es erwartet: Erst bewegen sie sich chaotisch, dann bauen sie eine Autobahn. Man beachte die Symmetrien. 


(II) Dann kommt die erste Überraschung: Vier Paare zeichnen gemeinsam ein immer größer werdendes Parallelogramm.

Spuren des Paares 2-East/2-East

Spuren des Paares 2-East/0-West

Spuren des Paares 0-West/2-East

Spuren des Paares 0-West/0-West

Die Entstehung der Vierecke sieht interessant aus: Die beiden Ameisen bauen gemeinsam eine immer größer werdende Figur und befinden sich dabei auf entgegengesetzten Seiten. 

(III) Das ist die zweite Überraschung: Vier Paare bewegen sich zyklisch.
3-South/3-South
1-North/1-North
3-South/1-North
1-North/3-South

Weitere Konstellationen    top
...... Wenn man die diagonale Anordnung zweier Quadrate betrachtet, die zwei Ameisen nach dem ersten Schritt erzeugen, so ergibt es neue Verläufe:
>Die Ameisen 1-North/3-South erzeugen nur symmetrische Figuren wie auch 3-South/1-North.
>Die Ameisen 2-East/2-East bewegt sich zyklisch mit der Periodenlänge 484. 
>1-North/2-East sind auch periodisch. Die Bewegung gleicht der eines rüttelnden Falken. 
>Besonders eindrucksvoll sind 2-East/2-East, denn erst nach etwa 45 000 Schritten beginnt der Autobahnbau. 


...... Mit zunehmender Anzahl der Ameisen gleicht das Gewimmel immer mehr einem Ameisenhaufen. In der nebenstehenden Ausgangsstellung kommt es manchmal zu einem neuen Phänomen: Eine Ameise baut an einer Autobahn, eine zweite kommt und "ribbelt" sie wieder auf. Das passiert zu Beginn der folgenden Konstellation.
Am Ende kommen nur zwei Ameisen zum Autobahnbau, die beiden anderen bewegen sich zyklisch im chaotischen Bereich. Dabei löschen und erzeugen sie schwarze Felder in immer gleicher Reihenfolge.

Verwandte Webseiten meiner Homepage

Apfelmännchen


Game of Life



Hüpfer


Langton-Ameisen im Internet       top

Deutsch

Alfred Nussbaumer
Langton-Ameise, Turmiten

Ian Stewart
Ameisen und die Erklärung der Welt  (Aus Spektrum der Wissenschaft August 1995, Seite 10)

Karl Kechele
Karls fleißige Ameise   (Applet)

Wikipedia
Ameise (Turingmaschine)


Englisch

Anahí Gajardo
The Industrious Ant of Langton 

Bill Casselman
Langton's Ant  (Applet)

Ed Pegg Jr (mathgames)
2D Turing Machines

Eric W. Weisstein (Mathworld)
Langton's Ant, Turmite

Ian Stewart
The Ultimate in Anty-Particles  (SCIENTIFIC AMERICAN July 1994)

Janne Blomqvist 
Langton's ant

J. C. Sprott
Langton's Ants

Scott Sutherland
Generalized Ants,  Download ants95
D. Gale, J. Propp, S. Sutherland, and S. Troubetzkoy: Further Travels with My Ants (.pdf-file)

Wikipedia
Langton's ant


Ich bedanke mich bei Stefan Trendafilov für den Hinweis auf die Langton-Ameisen.

Feedback: Emailadresse auf meiner Hauptseite

URL meiner Homepage:
http://www.mathematische-basteleien.de/

©  2004 Jürgen Köller

top