Ameise (Turingmaschine) - LinkFang.de





Ameise (Turingmaschine)


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.

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

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

Mehrfarbige Langton-Ameisen

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

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

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

Siehe auch

Weblinks

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

"Ameisenprogramme"

Einzelnachweise

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

Kategorien: Theoretische Biologie | Automatentheorie

Quelle: Wikipedia - http://de.wikipedia.org/wiki/Ameise (Turingmaschine) (Vollständige Liste der Autoren des Textes [Versionsgeschichte])    Lizenz: CC-by-sa-3.0

Änderungen: Alle Bilder mit den meisten Bildunterschriften wurden entfernt. Ebenso alle zu nicht-existierenden Artikeln/Kategorien gehenden internen Wikipedia-Links (Bsp. Portal-Links, Redlinks, Bearbeiten-Links). Entfernung von Navigationsframes, Geo & Normdaten, Mediadateien, gesprochene Versionen, z.T. ID&Class-Namen, Style von Div-Containern, Metadaten, Vorlagen, wie lesenwerte Artikel. Ansonsten sind keine Inhaltsänderungen vorgenommen worden. Weiterhin kann es durch die maschinelle Bearbeitung des Inhalts zu Fehlern gerade in der Darstellung kommen. Darum würden wir jeden Besucher unserer Seite darum bitten uns diese Fehler über den Support mittels einer Nachricht mit Link zu melden. Vielen Dank!

Stand der Informationen: August 201& - Wichtiger Hinweis: Da die Inhalte maschinell von Wikipedia übernommen wurden, ist eine manuelle Überprüfung nicht möglich. Somit garantiert LinkFang.de nicht die Richtigkeit und Aktualität der übernommenen Inhalte. Sollten die Informationen mittlerweile fehlerhaft sein, bitten wir Sie darum uns per Support oder E-Mail zu kontaktieren. Wir werden uns dann innerhalb von spätestens 10 Tagen um Ihr Anliegen kümmern. Auch ohne Anliegen erfolgt mindestens alle drei Monate ein Update der gesamten Inhalte.