Generalized Ants

This is some supplementary material to the paper

Briefly, an "ant" moves around on an infinite checkerboard, each square of
which we refer to as a "cell". Each cell in the plane is labeled as either
an **L**-cell or an **R**-cell (usually, one fills the plane with
**L**-cells to start). The ant starts out on the boundary between two
cells, and as it passes through each cell, it makes a 90 degree turn,
turning to the left in **L**-cells and to the right in **R**-cells,
and it changes the state of the cell it just left, switching **L**-cells
to **R**-cells, and vice versa. Following this simple set of rules gives
rise to some rather complicated behavior; the pattern of the ant's track
alternates between apparent chaos and symmetry, and eventually it starts to
build a "highway" moving off in a single direction.

The above described ant (and some variations) was originally studied by
Chris Langton (then at the Santa Fe
Institute, more recently a co-founder of the
Swarm Corporation).
Later, Jim Propp generalized the ant by considering each
cell to be in one of *n* different states: each ant has some "internal
programming" which tells it whether to turn left or right when the cell is
in that state. This "program" can be represented as a string of *n*
**L**s and **R**s, and the *k*th letter represents the ant's
action when it comes to a cell in state *k*. For example, Langton's
ant, described above, is a 2 state ant with the rule string **LR** (or in
binary 10, so we call this "ant number 2"). The 7 state ant with rule string
**LLRRRLR** (ant number 98) turns left when it visits a cell in state 1,
2, or 6, and right when it visits cells in state 3, 4, 5, or 7.

For all such generalized ants, one can readily see that if there is at least
one **L** and at least one **R** in the rule string, the track of the
ant will always be unbounded. And certain ants exhibit recurrent symmetry,
while others have apparently chaotic behavior.

You can either get a bit of a guided tour, get the whole batch in a zip archive, or select the files one at at time.

Also, see the Java simulators mentioned below, which you can run in Java-enabled browsers. Steve Witham has compiled some more links to software and articles.

A curses-based ant simulator which adds Truchet-tile output to
Jim Propp's
version.

You can get the source files for `ant.c` in a
zip archive,
or download the files
one at at time.

An X11-based interface using the Athena widget library.
(does not currently produce printable output).

You can get the source files for Xant in a
zip archive,
or download the files
one at at time,

A
**Java version**
of Langton's Ant, (rulestring 2) by
Steve Witham,

Another
**Java
version** of Langton's Ant, (rulestring 2) by
Bill
Casselman of the University of British Columbia.

An ant simulator for **Microsoft Windows**
written by Edward Richards. He
allows for a more general set of ant motions (multiple ants, forward and
backward motion as well as right and left, etc), so the numerical encodings
of his rulestrings are different than those discussed here. A very nice
program.

A simulator of Langton's 2-state ant (Ant 2) which runs on a
TI-82 graphing calculator
(written by Adam Beytin, c/o
mbeytin@umd5.umd.edu). *Not having
a TI-82, I haven't run this program.*

For further details, see

- D. Gale "The Industrious Ant",
*Mathematical Intelligencer*, vol. 15, no.2 (1993), pp 54-58. - D. Gale and J. Propp "Further Ant-ics",
*Mathematical Intelligencer*, vol. 16, no. 1 (1994), pp. 37-42. - D. Gale, J. Propp, S. Sutherland, S. Troubetzkoy, "Further Travels with
my Ant",
*Mathematical Intelligencer*, vol 17, no. 3 (1995), pp 48-56. - I. Peterson, "Travels of an Ant",
*Science News*, vol 148 no. 18 (1995), pp. 280-281. - L.A. Bunimovich and S. Troubetzkoy "Recurrence properties of Lorentz
Lattice Gas Cellular Automata",
*Journal of Statistical Physics*, vol. 67 (1992), pp. 289-302. - Additional
references, maintained by
Serge Troubetzkoy.