# Langton's ant

Langton's ant is a type of cellular automaton, or a simple form of artificial life, named after its designer, Christopher Langton. The ant lives on an infinitely large chessboard, each square of which can be either black or white. Two pieces of information are associated with this digital insect: the direction that it's facing, and the state of the square that it's currently standing on. Furthermore, the ant's behavior is completely described by three simple rules: (1) If it is on a black square, it makes a left turn. (2) If it is on a white square, it makes a right turn. (3) As it moves to the next square, the one it was on reverses color.

Interest in Langton's ant stems from the fact that despite being a completely
determined system governed by such extremely simple rules, the patterns
it produces are fantastically rich and complex. For the first 10,000 moves
or so, the Ant meanders around, building and then unbuilding structures
with little pattern to them. Then, near the end of this chaotic phase, the
ant begins to construct a diagonal highway off toward one the edge of the
board. In fact, this pattern stems from a sequence of 104 moves that, once
started, will go on forever. In the language of chaos theory, the pattern is a *stable attractor* for the system. Remarkably,
no matter what the initial arrangement of squares – even if the white
and black squares are set up randomly – the ant will end up building
a highway. The ant can be allowed to wrap around the edges of a finite board,
thus allowing it to intersect its own path, and it will *still* end
up building the highway. Are there any initial states that don't lead to
the diagonal-road-building loop? No exceptions have been found from experiments
– but proving it is quite another matter. Most mathematicians believe
there is no general analytical method of predicting the position of the
ant, or of any such chaotic system, after any given number of moves. Its
behavior cannot be reduced to the rules that govern it. In this sense, Langton's
ant is a very simple demonstration of the undecidability of the halting
problem.

The British mathematician Ian Stewart and biologist Jack Cohen, in their
book *Figments of Reality*,^{1} go a step further and use Langton's
ant as an analog of an essential stage in the evolution of complex
systems such as life: a stage in which the existence of chaotic behavior
contains the potential for the spontaneous emergence of unpredictable forms
of order.

### reference

1. Stewart, Ian and Cohen, Jack Cohen. *Figments of Reality*.
Cambridge, England: Cambridge University Press, 1997.