TOPICS
Search

Langton's Ant


Langton's ant

A 4-state two-dimensional Turing machine invented in the 1980s. The ant starts out on a grid containing black and white cells, and then follows the following set of rules.

1. If the ant is on a black square, it turns right 90 degrees and moves forward one unit.

2. If the ant is on a white square, it turns left 90 degrees and moves forward one unit.

3. When the ant leaves a square, it inverts the color.

LangtonsAntRoad

When the ant is started on an empty grid, it eventually builds a "highway" that is a series of 104 steps that repeat indefinitely, each time displacing the ant two pixels vertically and horizontally. The plots above show the ant starting from a completely white grid after 386 (left figure) and 10647 (right figure) steps. In the right figure, the highway is being constructed towards the lower right-hand corner. The fact that the ant's path is unbounded is guaranteed by the Cohen-Kung theorem. It is believed that no matter what initial pattern the ant is started on, it will eventually build a highway (although it might in principle take an extremely long time to reach this point). This would appear to follow naturally from the fact that Langton's ant is reversible, although it remains formally unproved (Beermann and Van Foeken).

In 2009, Benedetti posted a video of many behaviors.


See also

Cohen-Kung Theorem, Paterson's Worms, Turing Machine, Turmite

Explore with Wolfram|Alpha

References

Beermann, M. and Van Foeken, N. "Langton's Ant: An Exercise in Machine Design." http://cse.unl.edu/~mbeerman/ant.html.Benedetti, A. C. "Langton's Ant." Jan. 18, 2009. http://www.youtube.com/watch?v=1X-gtr4pEBU.Bunimovich, L. A. and Troubetzkoy, S. "Recurrence Properties of Lorentz Lattice Gas Cellular Automata." J. Stat. Phys. 67, 289-302, 1992.Gajardo, A. Dependence of the Behavior of the Dynamical System Langton's Ant on the Network Topology. Ph.D. Dissertation. Lyon, France: École Normale Supérieure de Lyon, 2001.Gajardo, A. "The Industrious Ant of Langton." http://www.ing-mat.udec.cl/~anahi/langton/.Gale, D. "The Industrious Ant." Math. Intell. 15, 54-58, 1993.Gale, D. and Propp, J. "Further Ant-ics." Math. Intell. 16, 37-42, 1994.Gale, D.; Propp, J.; Sutherland, S.; and Troubetzkoy, S. "Further Travels with My Ant." Math. Intell. 17, 48-56, 1995.Peterson, I. "Travels of an Ant." Sci. News 148, 280-281, 1995.Stewart, I. "The Ultimate in Anty-Particles." Sci. Amer. 271, 104-107, 1994.Sutherland, S. "Generalized Ants." http://www.math.sunysb.edu/~scott/ants/.Wolfram, S. A New Kind of Science. Champaign, IL: Wolfram Media, pp. 930-931, 2002.

Referenced on Wolfram|Alpha

Langton's Ant

Cite this as:

Weisstein, Eric W. "Langton's Ant." From MathWorld--A Wolfram Web Resource. https://mathworld.wolfram.com/LangtonsAnt.html

Subject classifications