The Return of the Ant and the Jeep

The industrious ant (see Chapter 10) has some sisters and cousins that are even more interesting. These generalized ants move from cell to cell in an infinite square grid. At any given moment, each cell in the grid is in some particular state. These states will be numbered 0 through (n — 1), where n is the number of allowed states. When an ant passes through a cell that is in state k, the state of the cell changes for k to (k + 1) modulo n, and the ant then leaves the cell, making either a left or a right turn relative to the direction it was traversing when it arrived at the cell. The ant is not free to choose which way it will go (right versus left). It must proceed in accordance with a rule-string of length n that is fixed for all time. The rule-string consists of n bits, numbered 0 through n — 1. When the ant is leaving a cell whose state used to be k (and is now (k + 1) modulo n), it turns right if r_k is 1 and left if r_k is 0, where r_k is the kth bit of the rule-string. This generalization of the ant seems to have been first considered by Greg Turk [1] and, independently, by Bunimovich and Troubetzkoy [2], who were building upon earlier work of E.G.D. Cohen [3].