Das Kefk Network Wiki befindet sich im Testbetrieb.

Ameise (Turingmaschine)

Aus Kefk.

Wechseln zu: Navigation, Suche
Bild:AMEIHUND Langtons Ameise.png
400px

Chris Langtons Ameise ist eine Turingmaschine mit einem zweidimensionalen Speicher und ein Beispiel dafür, dass ein deterministisches (das heißt nicht zufallsbedingtes) System aus einfachen Regeln zu sowohl komplex chaotischen, als auch komplex geordneten Strukturen führen kann.

Inhaltsverzeichnis

Der Algorithmus

Eine Ameise befindet sich ursprünglich auf einem zunächst weißen Raster und läuft in eine beliebige Richtung (in der Bilderserie nach unten). Wenn sie ein neues Feld betritt, so gelten folgende Regeln:

  1. Ist das Feld weiß, so färbt sie es schwarz und dreht sich um 90 Grad nach rechts.
  2. Ist das Feld schwarz, so färbt sie es weiß und dreht sich um 90 Grad nach links.

Danach läuft sie auf das nächste Feld in der neuen Blickrichtung.

In den ersten 10.000 Schritten entsteht ein komplexes, chaotisches Muster. Danach bildet sich eine regelmäßige Struktur . Der Algorithmus gibt symmetrische Regeln vor, jedoch sind die entstehenden Muster asymmetrisch. Dieses streng deterministische Muster ist nur durch obige Anweisungen reproduzierbar.

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

Siehe auch

Weblinks

"Ameisenprogramme"

Artikel

Wikipedia
 Dieses Dokument entstammt in seiner ersten oder einer späteren Version der deutschsprachigen Wikipedia. Es ist dort zu finden unter dem Stichwort Ameise_%28Turingmaschine%29, die Liste der bisherigen Autoren befindet sich in der Versionsliste; die Originalfassung kann dort auch bearbeitet werden. Alle Texte der Wikipedia und ihre Derivate stehen unter der GNU-Lizenz für freie Dokumentation.
Von „http://www.kefk.org/wiki/Ameise_%28Turingmaschine%29“
Persönliche Werkzeuge