Langton's Ant

There is a .pdf version of this page: DOWNLOAD

A good example of how a simple and totally determined system can produce both chaos and order is provided by an algorithm devised by Christopher Langton which has become generally know as Langton's Ant. This is one of the simplest forms of a class of dynamical systems known as cellular automata. Basically these consist of a grid of squares which either do or do not change colour according to a set of rules.

Imagine an ant walking on a large grid of squares. Initially all the squares are white. Whenever the ant walks onto a white square it turns green and the ant turns left. Whenever the ant walks onto a green square it turns white and the ant turns right.
The ant walks and walks and for about 10,000 moves it meanders around and creates this apparently chaotic pattern.
Then the ant starts walking in a complex closed loop of 104 moves. Each loop creates a step along this 'highway'.

Most of the examples given here were produced using a programme you can download a as Langton.zip. This programme allows you to play more complex games with the ant using more colours and different sequences of lefts and rights. It is also possible to have more than one ant walking at the same time. This programme seems to be available only via Windows Vista. There is another programme called ant-ology that can be downloaded at http://www.greenspirit.org.uk/resources/antology.exe.

This programme allows only one ant to walk but you can run all the single ant examples given below and, as the programme can be run much faster you can explore other ways of producing highways. Two examples of complex highways emerging from long random walks are given below>

Ant set up: + + + + + + + – – – – – – – + Random Walk c50,000 moves. Highway repeat step c3,900 moves	Ant set up: + + + – – – + + – – Random walk c875,000 moves. Highway repeat step c3,600 moves

The data included in each of the following examples are the initial state files produced by the programme in Langton.zip.

The initial state involves three ants walking the simple right/left pattern and starting from adjacent squares. The highway is produced by the co-operative efforts of two of the ants.	In this run the ant follows a more complex sequence of lefts and rights and creates a more complex highway

This run involves a single ant walking a complex right/left sequence. The ant walks a chaotic path for about 4500 moves. It then creates a complex highway looking rather like a stair. Each step of the stair requires over 800 moves. This is the most complex highway I have found so far.

These runs differ only in that one of the elements is displaced by a single grid square.	This run performs an endless loop of 7200 steps, including the building and destruction of a highway.

It is quite impossible to convey the richness of the almost endless possibilities inherent in the rules governing Langton's Ant. It is possible to play for hours and still be surprised. The significance of Langton's Ant is that it is a completely determined system, with relatively simple rules, but also with an almost infinite number of possible outcomes. Most of these are chaotic, some are ordered, and some contain elements of both order and chaos, as in the above examples.

There is no general analytical method of predicting the position of the ant after any given number of moves. The only way of finding out how any ant or combination of ants behaves and that is to let the ant or ants run. In spite of being constrained by relatively simple rules, Langton's Ant exhibits a measure of autonomy. Its behaviour cannot be reduced to the rules that govern it.

Ian Stewart and Jack Cohen (Figments of Reality, CUP, 1997) use Langton's Ant as an analogue representing an essential stage in the evolution of complex systems such as life: a stage in which the existence of chaotic behaviour contains the potential for the spontaneous emergence of unpredictable forms of order. The chaotic state provides the basis for the exploration of almost endless possibilities and is thus a significant feature in creative freedom.

A good web site for finding out more about Langton's Ant is:

http://www.math.sunysb.edu/~scott/ants/