Langton’s Ant

Langton’s ant starts off facing West in an arbitrary cell in an infinite grid of white cells. Every turn it checks the colour of the cell it is on and if it is white (which it is to start with) then it turns 90 degrees clockwise, colours the square under itself black and then moves forward one space. If the square it is on is black instead then it turns 90 degrees anti clockwise instead, again toggles the square it is on to the opposite colour and proceeds one space forwards.

From these simple rules the Ant will proceed to make a pattern which starts off really symmetrical:

The Ant frequently returns to the centre even though the border continues to expand outwards. This very ordered behaviour continues for about 500 moves until the symmetry breaks down and it acts in a really chaotic manner for about 10,000 moves. However, it gets even more interesting after that point because the Ant gets stuck in a loop of 104 moves which lead it to start on a journey taking it further and further South West in a structure we have dubbed a highway. Here's what it looks like:

This switch of behaviour from simple to chaotic and then to periodic highway building appears to happen even if you start off with a random finite spattering of black cells on the original grid. It is an open problem whether this will happen for any finite pattern but all simulations that have been run so far have begun highway building eventually. If you allow for an infinite number then a simple counterexample would be an infinite diagonal line of black cells which the ant would follow forever.

One thing we have proved is that the pattern will expand outwards indefinitely  (i.e. it will become infinitely large). Imagine that we do have a bounded region. Half the squares you will enter by moving vertically and half you will enter horizontally, think of the distribution a bit like a checkerboard. If we look at the very North East of the bounded region, then let's consider the case where you entered it horizontally. That means that you entered from the West and exited to the South which means that the cell was white. But if the region is finite then you must have a periodic sequence which means that you visit every cell an infinite number of times. This means that you will revisit that North East square again, but this time it is black and so you will head North from it instead, so it can't have been the most North Eastern cell in the region and we have a contradiction.

If it has a cell that you entered vertically then a similar argument works.

All of this is an example of a cellular automata which is one of my favourite areas of recreational mathematics. In common with other systems, Langton’s Ant gives surprising levels of complexity from a very small set of rules. There are lots of variations you can play around with by tweaking the movement rules, adding more ants or changing the grid (to a hexagon etc.). There is still a lot of room for exploration.