Langton's ant

Langton's ant

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 komplex geordneten Strukturen führen kann.

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

"Ameisenprogramme"


Wikimedia Foundation.

Игры ⚽ Нужно решить контрольную?

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

  • Langton's ant — after 11000 steps. A red pixel shows the ant s location. Langton s ant is a two dimensional Turing machine with a very simple set of rules but complicated emergent behavior. It was invented by Chris Langton in 1986 and runs on a square lattice of …   Wikipedia

  • Langton — may refer to:In places: *Langton, Cumbria, England *Langton, County Durham, England *Langton, Lincolnshire, England *Langton, North Yorkshire, England *Langton, Ontario, Canada *Langton, Pembrokeshire, WalesPeople with the surname Langton:… …   Wikipedia

  • Langton's loops — Langton s Loop, in the starting configuration. Langton s loops are a particular species of artificial life in a cellular automaton created in 1984 by Christopher Langton. They consist of a loop of cells containing genetic information, which flows …   Wikipedia

  • Ant (disambiguation) — An ant is a eusocial insect that belongs to the same order as wasps and bees.Ant, Ants, or ANT may refer to:*Ant hill, a pile of materials that build up at the entrances of the subterranean dwellings of ant colonies as they are excavated * The… …   Wikipedia

  • Christopher Langton — Born 1948/1949 Nationality American Alma mater …   Wikipedia

  • Fourmi De Langton — On nomme fourmi de Langton un automate cellulaire (voir : machine de Turing) bidimensionel comportant un jeu de règles très simples. Elle fut inventée par Chris Langton dont on lui a donné le nom. Elle constitue l un des systèmes les plus… …   Wikipédia en Français

  • Fourmi de langton — On nomme fourmi de Langton un automate cellulaire (voir : machine de Turing) bidimensionel comportant un jeu de règles très simples. Elle fut inventée par Chris Langton dont on lui a donné le nom. Elle constitue l un des systèmes les plus… …   Wikipédia en Français

  • Fourmi de Langton — On nomme fourmi de Langton un automate cellulaire (voir machine de Turing) bidimensionnel comportant un jeu de règles très simples. On lui a donné le nom de Chris Langton, son inventeur. Elle constitue l un des systèmes les plus simples… …   Wikipédia en Français

  • List of PSPACE-complete problems — Here are some of the more commonly known problems that are PSPACE complete when expressed as decision problems. This list is in no way comprehensive. Games and puzzles Generalized versions of: Amazons· Atomix· Geography· Gomoku· Hex· Reversi·… …   Wikipedia

  • Wireworld — [ diodes, the above one in conduction direction, the lower one in reverse biasing] Wireworld is a well known cellular automaton first proposed by Brian Silverman in 1987, as part of his program Phantom Fish Tank. It subsequently became more… …   Wikipedia

Share the article and excerpts

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