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 and moves forward one unit.
2. If the ant is on a white square, it turns left and moves forward one unit.
3. When the ant leaves a square, it inverts the color.
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 (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.
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. News148, 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.
and moves forward one unit.
and moves forward one unit.
(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).
