« Autour de la Lune: Web Edition Updated | Main | Cellular Automata Laboratory: Reproduction, Evolution, Abiogenesis, and Sex »

## Tuesday, June 20, 2017

### Cellular Automata Laboratory: Langton's Ant

I have added another new rule to Cellular Automata Laboratory (CelLab): Langton's Ant. This rule was discovered by Christopher Langton in 1986, and is one of the simplest known moving-head Turing machine rules which exhibits complex behaviour.

It is a two-dimensional Turing machine with a head (ant) that moves on a map of cells which can be in one of two states. In each generation, the head moves to an adjacent cell, inverting the state of the cell it departs. The head can move in one of the four directions in the von Neumann neighborhood; the direction it moves is set by the current state of the head. Upon moving to a new cell, the head adjusts its direction by turning clockwise if the cell's state is zero and counterclockwise if it is one.

When started with an all-zero map, the head starts by tracing
out a lacy pattern exhibiting symmetries, but then, as the
pattern grows, appears to be following a random walk, occasionally
adding to the borders of the pattern. After around 10,000
generations, however, the head will begin to create a
“highway” which extends in a diagonal direction in
a cycle of 104 generations. This is an example of spontaneous
emergence of order after a long period of apparently chaotic
behavior. If run on an infinite map, the highway would extend
without bound, but on our wrap-around map, it will eventually
collide with the original random pattern, producing interesting
interactions. All starting configurations which have been
tested eventually produce a highway, but it has not been proved
that every possible configuration does so. It has, however, been
proved that the pattern always grows without bound in some manner.
Try starting the rule on the **square** pattern and watch how
it evolves into a lattice of ordered highways and burl-like
intersections.

**Run the Langton's Ant rule in CelLab**

Posted at June 20, 2017 23:09