Langton's ant

Langton's ant is one of the cleanest demonstrations of an uncomfortable idea: you don't need a plan to produce structure. There is a grid, an ant and two rules. Nothing else. After about ten thousand steps, the drawing that appears looks nothing like the rules that produced it.

Two rules

The world is an infinite grid of white or black cells. The ant occupies one cell and faces one of the four directions. At each step it does exactly this:

current cell	turn	new color
white	90° right	black
black	90° left	white

After turning and flipping the color, the ant moves one cell forward in whatever direction it is facing. There is no memory, no search, no internal representation of the world. The grid is all the memory there is.

The rule was invented in 1986, in the context of cellular automata and artificial life. It is a particular case of a turmite: a Turing machine that moves over a two-dimensional tape instead of reading it left to right.

The highway

At first the trail is symmetric and chaotic. For thousands of steps the ant seems to wander aimlessly, building and destroying blocks. Then, around step 10,000 on an empty grid, something changes: the pattern orders itself and the ant starts repeating a 104-step cycle. Each cycle shifts the drawing two cells diagonally. That periodic structure is known as Langton's highway.

The highway is not programmed anywhere. It is a consequence of the interaction between the ant and the trails it left behind itself. A cell that the ant painted thousands of steps ago changes the turn it will take today. The system has memory, but the memory is distributed across the terrain.

There is no known closed description of the whole trajectory. Nor is it proven that every finite initial configuration ends in a highway; the computational evidence is overwhelming, but the general problem remains open. What is known is that generalizations with more colors and rules can be Turing-complete: the family of ants can simulate a Turing machine. The original two-color version is a special case that still refuses to reduce to a simple formula.

Why it matters

The ant is a reminder that complexity does not require a complex rule. It is also a test bench for more general questions: when does a local system produce global structure? How does predictability relate to computability? What does it mean for a system to “compute” without having a purpose?

In computer science it appears next to cellular automata, discrete dynamical systems and unconventional computing. In all those cases the lesson is similar: the interesting behavior is not in the components, but in the interactions.

A minimal implementation

The code fits in a few lines if you use complex numbers for the position and the direction. Multiplying by i turns 90° one way; multiplying by −i turns it the other. The black set holds the black cells.

black = set()
pos = 0j
direction = 1  # east

for _ in range(15_000):
    if pos in black:
        direction *= 1j      # left
        black.remove(pos)
    else:
        direction *= -1j     # right
        black.add(pos)
    pos += direction

To draw it, walk black and paint each pair (int(z.real), int(z.imag)) as a cell. The interesting part is not the render, but the fact that those four lines produce the figure above.

Closing

The ant doesn't know it is building a highway. It just obeys two rules. That distance between the rule and the result is exactly what makes it worth studying.