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,¹ 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.