Cybermyrmecology

Click to jump to the instructions or the background discussion. This applet requires a browser which can run applets developed with the JDK 1.1.5 such as Netscape 4.5, appletviewer or HotJava.

Try running ant 2 (the default ant) to steps 184, 368, 472, and 10,000 to see some interesting patterns or features. Another pair of interesting targets are ant 9 at step 38,836, and ant 12 at step 16,464.

Instructions

The controls are displayed below the cellular automata (CA) itself:

Start: Set the automaton in motion. When pressed the Start button will become a Stop button.
Stop: Stop the automaton's motion. When pressed the Stop button will revert to being the Start button.
Step: Perform one step of calculation. This is equivalent to starting and then stopping the automaton after one unit of time has passed.
Reset: Return the automaton to its initial state.
Run to step: A target step (such as step 25) can be input here and when the automaton is started it will run to that step and then stop.
Display Truchet Tiles: When this checkbox is set, each cell will have two arrows added to it. See below for a more detailed describtion of what Truchet tiles are.
Display Ant: Display the ant's location as a white square with an arrow in it demarking the ant's direction.
Display State: Display each cell's state as a square whose color denotes the cell state. The default state of each cell is zero (black).
Highlight Principal Contour: This checkbox is only enabled if the Truchet tiles are displayed. When set, highlight (in black) the Truchet contour through the ant's initial location.
Ant to use: Specify as a decimal number the ant to use for the next run of the automaton. The rule string can be derived from the ant number by converting that number to binary (1 == R, 0 == L). When a new number is input here the "Ant rule string" text field to the right will be updated to display the rule string of the input ant.
Ant rule string: Specify as a rule string (a string of 'R' and 'L' characters) the ant to use for the next run of the automaton. This text field has the same effect as the "Ant to use" field to its left, but it avoids having to convert a decimal number to binary to check what rule string is in use. When a new rule string is input here the "Ant to use" field will be updated to display the number of the ant input here.
Delay per frame: The automaton will wait for this number of milliseconds per step before proceeding to the next step. This has the effect of slowing the automaton down.

Background

This applet implements a virtual "ant" which follows a simple rule: when it enters a cell it turns either left or right based on the state of the cell. The simplest example of this is ant 2 (which is the default ant in the applet). This ant is called ant 2 because its rule string is RL, which is a binary 2 if you substitute 1 for R and 0 for L. Each letter in the rule string corresponds to a cell state - so therefore the number of states the cells can be in is equal to the size of the rule string. If we number the cell states starting from 0 as 0, 1, 2, ... then each letter in the rule string determines which way the ant turns when it enters a cell when the rule string is read from right to left:

Rule string:     R L                  R L L R              R R L L
Cell states:     1 0                  3 2 1 0              3 2 1 0
            Ant 2 (binary 10)   Ant 9 (binary 1001)  Ant 12 (binary 1100)

For example, the cells that ant 2 traverses are either in state 0 or state 1, depicted in either black (state 0) or red (state 1). When the ant enters a black (state 0) cell it looks up location 0 in its rule string (L) and therefore turns left. Similarly, when it enters a red (state 1) cell it looks up location 1 in its rule string (R) and turns right.

Here's the complete list of states and the colors they're displayed in:

0 Black

1 Red

2 Green

3 Blue

4 Yellow

5 Magenta

6 Cyan

7 Orange

8 Pink

9 Light Grey

10 Grey

11 Dark Grey

Truchet Tiles

Because the ant turns 90 degrees each time it turns, you can divide up the grid into horizontal and vertical columns. These columns are denoted by the cell's Truchet tile. There are four tiles, two horizontal tiles (a left orientation and a right orientation) and two vertical tiles (again in left and right orientations). When the ant enters a cell its handedness is flipped (if the cell had a left orientation it's changed to a right orientation and vice versa).

Truchet tiles are used to prove theorems about the properties of the ant. See the paper "Further Travels with My Ant" by Gale et al. for several applications of Truchet tiles to proofs of ant properties.

Bibliography

I. Peterson, "Travels of an Ant", Science News volume 148 number 18 (October 28, 1995), pp. 280-281.
S. Sutherland, Ants WWW site.
D. Gale, J. Propp, S. Sutherland, and S. Troubetzkoy, "Further Travels with My Ant", Mathematical Intelligencer volume 17 number 3 (1995), pp. 48-56.

J. Scott Hofmann

0	Black
1	Red
2	Green
3	Blue
4	Yellow
5	Magenta
6	Cyan
7	Orange
8	Pink
9	Light Grey
10	Grey
11	Dark Grey