Langton's ant

The ant is a Turing machine with a two-dimensional memory and was developed in 1986 by Christopher Langton. It is an example that a deterministic ( ie non-random conditional ) may adopt system of simple rules both for humans visually surprising randomly appearing and periodical states.

• Initial: The ant enters the white field, the far left, is located at the top of the table in its center and in its downward orientation;
• Step 1.1: The ant makes the dot in the center of the grid black and rotates 90 degrees to the right, it points away from the viewer's perspective ie to the left;
• Step 1.2: The ant is running on the dot left of center;
• Step 2.1: The ant makes the dot to the left of the middle black and rotates 90 degrees to the right, so it is facing up;
• Step 2.2: The ant is running on the grid point to the left of the start point.

• 4.1 " ants programs "

The algorithm

The ant is located in a grid consisting of square fields, which can be either black or white. In the initial situation, all the fields are white and the ant looks in a certain direction ( in this illustration to bottom). The transition to the next state according to the following rules:

In the first 500 steps occur repeatedly in a symmetrical pattern. Then the ant is a complex, chaotic pattern while around 10,000 steps. Finally, she goes on to some, a regular structure ( " ant trail " ) to build: You gets all 104 steps to the same state; diagonally shifted by 2 fields.

The system may also be considered as a cellular automaton, in which a single active cell knows additional states ( the orientation of the Ant ), and wherein in each step change only two cells (source and destination field of the ant ).

Generalizations

Multicolored Langton Ants

Greg Turk and Jim Propp studied an extension of the classical Langton Ant. The ants then traverse a cycle of left and right movements, which is described by a rule which consists of a finite sequence of "L" ( left movement ) and "R " ( right) keys. For a rule with N character ' L ' or ' R' n different colors are used for illustration. The original Langton Ants are described by the rule ' RL'.

Some rules produce symmetrical figures, other seemingly completely chaotic, which is partially unknown whether these generate an ant - road to sufficiently many steps.

• Examples of multi-colored Langton Ants:

LLRR: Balanced growth.

LLRRRLRLRLLR: Creates a trail.

RRLLLRLLLRRR: Creates a filled, growing triangle.

Turmiten

If the ant additional states may take ( in addition to their orientation), we obtain a further generalization. For each combination of state ants, ants direction and field color is a rule for the next step is given. The combination of the name of Alan Turing and Turmiten - Mitendecker Greg Turk with mite, the English word for mite, the term was turmite ( pronounced the same in English as termite ) was formed.

• Examples of Turmiten:

Semi- chaotic growth.

Chaotic growth, followed by construction of an ant trail.

Chaotic growth with texture.

Creates a Fibonacci spiral.