OCA:Langton's ant
(click above to open LifeViewer)
Langton's ant is a two-dimensional Turing machine invented by Chris Langton in 1986 with a very simple set of rules but complex emergent behavior:
- At a white square, turn 90° clockwise, flip the color of the square, move forward one unit
- At a black square, turn 90° counter-clockwise, flip the color of the square, move forward one unit
Langton's ant can also be described as a cellular automaton, where the grid is colored black or white and the "ant" square has one of eight different states assigned to encode the combination of black/white state and the current direction of the ant.
Behavior
These simple rules lead to complex behavior. Three distinct modes of behavior are apparent when starting on a completely white grid:
- Simplicity. During the first few hundred moves it creates very simple patterns which are often symmetric.
- Chaos. After a few hundred moves, a large, irregular pattern of black 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 repeats indefinitely.
| The highway, which can be thought of as a wickstretcher moving at 2c/104 diagonally (click above to open LifeViewer) |
Computational Properties
In 2000, Gajardo et al. showed a construction that calculates any boolean circuit using the trajectory of a single instance of Langton's ant.
Extension to multiple ants
Multiple Langton's ants can co-exist on the 2D plane, and their interactions give rise to complex, higher-order automata that collectively build a wide variety of organized structures.
An oscillator that uses multiple ants is called a colony.
| A collection of moving patterns using multiple ants (click above to open LifeViewer) |
Variations
Langton's Ant is one of many "turmite" rules.
Emulation by other rules
The R-pentomino traces the path of dots left by a single langton's ant in the isotropic non-totalistic rule B3-cjkq4knqy5cnr7/S02-cn3-ak4eiq5kq6e7e.
External links
- Langton's Ant Society (discussion thread) at the ConwayLife.com forums
- Langton's ant at Wikipedia