A dance with 104 steps
Langton’s Ant is an interesting example of a cellular automaton.1 It was first discovered by American computer scientist Chris Langton in 1986. The ant travels around an extremely large grid of squares which can be either black or white. After a while it teaches itself to dance in what seems to be a coordinated way.
The rules
The Ant can travel in any of the four cardinal directions at each step it takes. It moves according to the rules below:
At a white square, turn 90° clockwise, flip the colour of the square, move forward one unit
At a black square, turn 90° counter-clockwise, flip the colour of the square, move forward one unit
With such simple rules we would expect some sort of repetitive pattern to emerge fairly quickly, but this isn’t what happens.
In the first 200 steps our little friend just wanders around close to its starting point leaving a changing trail which looks to show no signs of a pattern. The Ant’s first 200 moves.
Unlike humans, ants don’t get bored doing mundane repetitive tasks. That’s why we invented computers.
After 400 steps not much changes, it is still a random walk, but the Ant seems to have slightly enlarged its range.
Ditto after 1000 steps (most reasonable people would have given up by now)
Ditto after 2000 steps
But the penny finally drops after 10,000 steps. In a eureka moment the ant has finally done its groundwork and launches into a dance of 104 steps, repeated time and time again but offset to the south-east (if it started facing north). The red pixel show where the Ant is. It will continue indefinitely in that mode.
What does this mean?
The first thing to notice is that complex behaviour can emerge from very simple systems.
Secondly note that the pattern only emerges after a very large number of generations. Even though it is a simple system the resulting behaviour only becomes evident after the Ant gets its act together.
If a simple system with just a few rules can lead to complex behaviour then why are we surprised that a system with only 22333 instructions can lead to something as complex as a Shakespearean sonnet?
It is also notable that the pattern only emerges after 10,000 iterations. Humans and even the most dedicated mathematicians would have given up well before the Ant shows its hidden order.
Imagine trying to demonstrate a number is transcendental (eg like pi, it does not contain a repeating pattern of digits.) You calculate your number to 9,999 decimal places and have to stop as your screen it full. You say ‘enough is enough’. Then somebody else who has more room on their bigger screen for 11,000 digits shows that your number continues beyond 10,000 with the sequence 22333223332233322333 indefinitely.
Where does number 104 steps come from?
Let’s see if we can find some clues as to why our Ant decided on this particular number of steps in its dance.
From Wikipedia, the free encyclopedia
104 may refer to:
104 (number), a natural number
AD 104, a year in the 2nd century AD
104 BC, a year in the 2nd century BC
104 (MBTA bus), Massachusetts Bay Transportation Authority bus route
Hundred and Four (or Council of 104), a Carthaginian tribunal of judges
104 (City of Edinburgh) Field Squadron, Royal Engineers, a Scottish military unit
104 (Tyne) Army Engineer Regiment, Royal Engineers, an English military unit
104 (barge), cargo ship in service in the 1890s
Some interesting stuff here but none of it seems to have much to do with ants.
I like to factorise numbers as a way of understanding where they come from. 104 has to prime factors 2 and 13. The two is not surprising but 13 is interesting. Why 13 and not 23? Perhaps ants have 13 chromosomes? Stranger things happen.
What is much more likely that the explanation lies somewhere in the depths of group theory.
For example the image below, derived from putting four rectangles in a row and then joining each corner to all of the others has 104 internal regions.
More about Langton’s Ant
There are many variations and extensions of Langton’s Ant. See this Wikipedia article
Cellular automata consist of a regular grid of cells, where each cell can have a finite number of states. The system is determined by a set of rules that specify how the state of each cell changes over time based on the states of its neighbours. The most famous CA is Conway's Game of Life, which consists of a two-dimensional grid of cells that can be either "alive" or "dead," and evolves according to four simple rules. Despite their simplicity, cellular automata can exhibit a wide range of behaviours, from static patterns to chaotic dynamics.
Cellular automata demonstrate self-organisation, where simple rules can give rise to complex phenomena.
In physics, cellular automata have been used to model the behaviour of fluids, gases, and solids, and to study phase transitions and critical phenomena.
In biology cellular automata have been used to simulate the growth of organisms, the spread of diseases, and the evolution of populations.
In computer science cellular automata have been used to design algorithms, to generate random numbers, and to simulate networks.
In the social sciences cellular automata have been used to study the emergence of collective behaviour, the diffusion of information, and the dynamics of opinion formation.