Langton’s ant revisited

Langton’s ant is a two-dimensional generalisation of a Turing machine, known as a turmite (a portmanteau of ‘Turing’ and ‘mite’, as well as being a pun on ‘termite’), renowned for its simple rules and interesting behaviour. Specifically, it has one state and two colours, and obeys the following rules:

• If the ant is on a white square, turn right and paint the square black;
• If the ant is on a black square, turn left and paint the square white.

The behaviour for the first 200 steps is shown in this animation:

It transpires that in about 10000 steps, the ant’s behaviour becomes periodic, building a diagonal highway ad infinitum. It has been proved that no initial configuration can lead to a bounded (cyclic) route, but it is unknown as to whether there are other attractors as well as the simple highway.

The 349th problem on Project Euler asks how many black squares are produced in 10^18 steps. This can be done with a little work once the periodic behaviour is known. However, we’re too lazy to actually do the relevant periodicity checking and linear extrapolation, so we’ll instead employ a minimal-effort solution:

1. Run the cellular automaton program Golly, and open ‘Patterns/Other-Rules/Langtons-ant.rle’.
2. Execute ‘goto.py’ and enter ‘1000000000000000000’ into the dialogue box.
3. Press the ‘enter’ button and wait less than one second for the miracle of the HashLife algorithm to simulate all 10^18 generations.
4. Read off the population count, and adjust according to whether the ant is on a white or black square.

(I’m not going to give the numerical value here, as that would be a spoiler for anyone who wants to solve the problem legitimately.)

Some of the earlier problems on Project Euler have one-line solutions in Mathematica, but this is probably the ‘hardest’ problem to be trivialised by possessing powerful software.

Tim’s turmite challenge

If we allow the two-dimensional Turing machine to have two states instead of one, there is an explosion of rich and complicated behaviour. Ed Pegg asked for the one which lasts the longest before becoming predictable (Langton’s ant, taking 10000 generations, is a weak lower bound).

Shown above is a 2-state machine which takes over 4 million steps before settling into a periodic cycle. Since then, the record has been smashed twice in a short space of time, with the current winner taking 240 million generations of chaotic behaviour before finally building two highways in opposite directions:

Zoomed-out image of the final state of Georgi Gochev’s 240-million-step turmite

Tim Hutton and Ed Pegg have set the challenge of finding turmites with longer stabilisation times, encouraging a distributed effort. If you’re interested, follow the instructions on the relevant page.