Ants
Romanian version of this page, translated by Alexandra Seremina, courtesy Azoft.

Generalized Ants

This is some supplementary material to the paper Further Travels with My Ant by David Gale, Jim Propp, Scott Sutherland, and Serge Troubetzkoy, which appears in the Summer 1995 issue of the Mathematical Intelligencer. In this paper, the some behavior of a cellular automaton called an "ant" is discussed. The ant moves about, and in each "cell", the ant turns right or left, depending on the the state of the cell, and then changes the state of the cell according to certain prescribed rule strings.


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 Ls and Rs, and the kth 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.


Pictures of some states of the ants.
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.


Some source code for an ant simulator that will run various types of computer systems.

* 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