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 zu sowohl komplex chaotischen, als auch komplex geordneten Strukturen führen kann.

AMEIHUND Langtons Ameise.png
Die ersten Schritte laufen folgendermaßen ab:
  • Initial: Die Ameise betritt das weiße Feld in der Mitte und schaut nach unten (nicht dargestellt);
  • Schritt 1.1: Die Ameise macht das Feld in der Mitte schwarz und dreht sich um 90 Grad nach rechts, sie schaut also nach links;
  • Schritt 1.2: Die Ameise läuft auf das Feld links von der Mitte (in Bild 1 dargestellt);
  • Schritt 2.1: Die Ameise macht das Feld links von der Mitte schwarz und dreht sich um 90 Grad nach rechts, sie schaut also nach oben;
  • Schritt 2.2: Die Ameise läuft auf das Feld links oben der Mitte (in Bild 2 dargestellt).

Inhaltsverzeichnis

Der Algorithmus

Eine Ameise befindet sich ursprünglich auf einem zunächst weißen Raster und sieht in eine beliebige Richtung (in der Bilderserie zuerst 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, chaotisch erscheinendes 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

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

"Ameisenprogramme"


Wikimedia Foundation.

Schlagen Sie auch in anderen Wörterbüchern nach:

  • Ameise (Begriffsklärung) — Der Begriff Ameise steht für ein Insekt, siehe Ameisen das Wappentier in der Heraldik, siehe Ameise (Wappentier) eine Marke des Unternehmens Jungheinrich für Hubwagen eine Turingmaschine, siehe Ameise (Turingmaschine) einen Algorithmus, siehe… …   Deutsch Wikipedia

  • Turingmaschine — Die Turingmaschine ist ein von dem britischen Mathematiker Alan Turing 1936 entwickeltes Modell, um eine Klasse von berechenbaren Funktionen zu bilden. Sie gehört zu den grundlegenden Konzepten der Theoretischen Informatik. Das Modell wurde im… …   Deutsch Wikipedia

  • Universelle Turingmaschine — Die Turingmaschine ist ein von dem britischen Mathematiker Alan Turing 1936 entwickeltes Modell, um eine Klasse von berechenbaren Funktionen zu bilden. Sie gehört zu den grundlegenden Konzepten der Informatik. Das Modell wurde im Rahmen des von… …   Deutsch Wikipedia

  • Langton-Ameise — Christopher 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… …   Deutsch Wikipedia

  • Langton Ameise — Christopher 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… …   Deutsch Wikipedia

  • Turing-Maschine — Die Turingmaschine ist ein von dem britischen Mathematiker Alan Turing 1936 entwickeltes Modell, um eine Klasse von berechenbaren Funktionen zu bilden. Sie gehört zu den grundlegenden Konzepten der Informatik. Das Modell wurde im Rahmen des von… …   Deutsch Wikipedia

  • Turingmodell — Die Turingmaschine ist ein von dem britischen Mathematiker Alan Turing 1936 entwickeltes Modell, um eine Klasse von berechenbaren Funktionen zu bilden. Sie gehört zu den grundlegenden Konzepten der Informatik. Das Modell wurde im Rahmen des von… …   Deutsch Wikipedia

  • Zellularautomat — Zelluläre oder auch zellulare Automaten dienen der Modellierung räumlich diskreter dynamischer Systeme, wobei die Entwicklung einzelner Zellen zum Zeitpunkt t+1 primär von den Zellzuständen in einer vorgegebenen Nachbarschaft und vom eigenen… …   Deutsch Wikipedia

  • Zellulare Automaten — Zelluläre oder auch zellulare Automaten dienen der Modellierung räumlich diskreter dynamischer Systeme, wobei die Entwicklung einzelner Zellen zum Zeitpunkt t+1 primär von den Zellzuständen in einer vorgegebenen Nachbarschaft und vom eigenen… …   Deutsch Wikipedia

  • Zelluläre Automaten — Zelluläre oder auch zellulare Automaten dienen der Modellierung räumlich diskreter dynamischer Systeme, wobei die Entwicklung einzelner Zellen zum Zeitpunkt t+1 primär von den Zellzuständen in einer vorgegebenen Nachbarschaft und vom eigenen… …   Deutsch Wikipedia

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”