Ant (Turing machine)

from Wikipedia, the free encyclopedia

The ant is a Turing machine with a two-dimensional memory and was developed in 1986 by Christopher Langton . It is an example of the fact that a deterministic (i.e. not random) system with simple rules and a simple initial state can assume states that appear visually disordered to humans as well as states that appear regularly.

AMEIHUND Langtons Ant.png
The first steps are as follows:
  • Initial: The ant enters the white field, which is on the far left, at the top, in the middle of the table and points downwards in its orientation;
  • Step 1.1: The ant turns the grid point in the middle of the grid black and turns 90 degrees to the right, so it points to the left from the observer's point of view;
  • Step 1.2: The ant runs to the grid point to the left of the center;
  • Step 2.1: The ant makes the grid point to the left of the center black and rotates 90 degrees to the right, so it points upwards;
  • Step 2.2: The ant runs to the grid point on the left over the starting point.

The algorithm

The ant moves in an infinite square grid of fields that can be either black or white. In the initial situation, all fields are white and the ant is sitting on one of the fields and looking in a certain direction (downwards in this illustration). The transition to the next state takes place according to the following rules:

  1. On a white square, turn 90 degrees to the right; on a black field turn 90 degrees to the left.
  2. Change the color of the field (white to black or black to white).
  3. Go to the next field in the current viewing direction.

In the first approx. 500 steps, symmetrical patterns appear repeatedly. Then the ant forms a complex, chaotic pattern for around 10,000 steps. Finally she goes over to building a regular structure (“ant road”): every 104 steps it gets into the same (local) state; shifted diagonally by 2 spaces and builds the road to infinity.

Generalizations

Multicolored long-tone ants

Greg Turk and Jim Propp investigated a generalization of the classic Langton ant. A field goes through a cycle of two or more field states (colors): Before the ant goes to the next field, it changes the state of the current field to the next in the cycle. A swivel direction is assigned to each state, either to the left or to the right by 90 °. The original Langton ant is described by the rule 'RL'.

Some rules create symmetrical images, others seem to be completely chaotic, although it is partly unknown whether these create an ant road after a sufficient number of steps.

  • Examples of multi-colored long-tone ants:

  • RLR: Chaotic Growth.

  • LLRR: Symmetrical Growth.

  • LLRRRLRLRLLR: Creates an ant trail.

  • RRLLLRLLLRRR: Creates a filled, growing triangle.

Turmites

If the ant can assume additional states (besides its orientation), one obtains a further generalization. A rule for the next step is given for each combination of ant condition, ant direction and field color. The term turmite (pronounced the same as termite in English ) was formed from the combination of the names of Alan Turing and Turmite co-discoverer Greg Turk with mite , the English word for mite .

  • Examples of Turmites:

  • Spiral growth.

  • Semi-chaotic growth.

  • Chaotic growth with subsequent construction of an ant road.

  • Chaotic growth with texture.

  • Creates a Fibonacci spiral .

Other grids

Instead of a square grid, triangular, hexagonal and pentagonal grids (the latter made of irregular tileable pentagons) are also conceivable. Some simulations in Linux screen savers also offer this option.

  • Triangular grid, classic rules, 36 steps

  • Triangular grid, classic rules, 60,000 steps

  • Triangular grid, classic rules, 6,000,000 steps

Web links

Commons : Langton's ant  - collection of images, videos and audio files

Ant programs

Individual evidence

  1. ↑ Clemens Hovekamp: Langton ant, symmetrical pattern
  2. ↑ Rudy Rucker: Artificial Life Lab. June 5, 1993, accessed October 13, 2018 .