Langton's ant is a two-dimensional Turing machine with a
very simple set of rules but complicated emergent behaviour. It is often used to
point out the weakness of reductionism in science: The Ant lives according to simple rules,
yet these do not really help to understand its behaviour...
It was invented by Chris Langton in 1986.
Squares on a plane are coloured variously either red or white. We arbitrarily identify one square as the "ant". The
ant can travel in any of the four cardinal directions at each step it takes. The ant moves according to these rules:
- At a white square, turn 90° right, toggle the colour of the square, move forward one square
- At a red square, turn 90° left, toggle the colour of the square, move forward one square
These simple rules lead to complex behaviour:
- Simplicity:
- During the first few hundred moves it creates very simple patterns which are often symmetric.
- Chaos:
- After a few hundred moves, a big, irregular pattern of red and white squares appears. The ant traces a
pseudo-random path until around 10,000 steps.
- Emergent order:
- Finally the ant starts building a recurrent "highway" pattern of 104 steps that repeat indefinitely. All finite
initial configurations tested eventually converge to the same repetitive pattern, suggesting that the "highway" is
an attractor of Langton's ant, but no one has been able to prove that this is true for all such initial
configurations. It is only known that the ant's trajectory is always unbounded regardless of the initial
configuration.
Tested on MacOSX 10.7.5: works OK in current Chrome, Safari and Opera, and mostly in all others. Problem in some versions of Firefox (e.g. cant set squares, have to switch
apps or tabs to force canvas update in version 22).