Langton's ant

Langton's ant, named after its discoverer Chris Langton, is a 2-dimensional Turing machine with 2 symbols and 4 states. It consists of a grid of cells along with an ant that is located on one of these cells and faces one of the four cardinal directions.

In each step, the ant moves according to the following rules:

Since the ant switches between horizontal and vertical orientations at each step, the cells of the grid split up in a checkerboard pattern into two sets: those cells which are always entered vertically (exited horizontally), and those cells which are always entered horizontally (exited vertically).

Unboundedness

It has been proven that the ant's trajectory is unbounded regardless of the initial configuration. The proof is as follows:1

It is easy to check that the Theory of Everything for Langton’s Ant is time-reversible. That is, the current pattern and heading determines the past uniquely as well as the future. Any bounded trajectory must eventually repeat the same pattern, position, and heading; and by reversibility such a trajectory must be periodic, repeating the same motions indefinitely. Thus every cell that is visited must be visited infinitely often.

The ant’s motion is alternately horizontal and vertical, because its direction changes by ±90° at each step. Call a cell an H-cell if it is entered horizontally, and a V-cell if it is entered vertically. The H- and V-cells tile the grid like the black and white squares of a checkerboard.

Select a square M that is visited by the ant, and is as far up and to the right as possible, in the sense that the cells immediately above and to the right of it have never been visited. Suppose this is an H-cell. Then M must have been entered from the left and exited downward, and hence must have been white. But M now turns black, so that on the next visit the ant exits upwards, thereby visiting a square that has never been visited. A similar problem arises if M is a V-cell. This contradiction proves that no bounded trajectory exists.

It has also been proven that, for any initial configuration, the set of cells that are visited infinitely often has no corners. A corner of a set is a cell where at least two neighbors are not in the set, and these are not opposite to each other.4 Since a cell is entered and exited at right angles, this implies that every cell that is visited infinitely often has at least 3 neighbors that are visited infinitely often.

P-hardness and universality

It has been proven that ant's trajectory can calculate any boolean circuit, proving the system is P-hard.2 With an infinitely repeating initial configuration, the ant can simulate cellular automata and is thus computationally universal.

Open problems

Despite the simplicity of its rules, the ant exhibits complex emergent behavior. There are many open problems regarding this behavior. Here are two examples which seem to hold for any finite initial configuration:

The third conjecture implies the first two. These conjectures have held for all finite initial configurations tested so far, but they remain unproven.

The behavior of ants with a different set of rules has also been studied.3

Interactive demo

Mouse controls:

Scroll Zoom camera
Drag Pan camera
Double tap Toggle cell

The conjecture that Langton's ant builds a highway for any finite starting configuration resembles the Collatz conjecture. Perhaps, as Paul Erdős said of the latter, mathematics is not ready for this problem.

References

  1. Ian Stewart. Travels with my ant.
  2. Anahi Gajardo, Andres Moreira, Eric Goles. Complexity of Langton's ant.
  3. David Gale, Jim Propp, Scott Sutherland, Serge Troubetzkoy. Further travels with my ant.
  4. S. Troubetzkoy. Lewis–Parker Lecture 1997 The Ant. Alabama J. Math. 21(2) (1997) 3–13 4.