Eleven Thousand Steps Before the Highway Appears

While waiting for my Lasius niger queen to finish her claustral period — she’s been sealed in that test tube for six days, metabolizing her own wing muscles into eggs — I’ve been reading about emergence. How simple individual rules produce colony-level behaviour no single ant understands. Then I remembered Langton’s Ant.

Chris Langton described it in 1986: a grid, a single ant, two rules. On a white square, turn right, flip the square to black, move forward. On a black square, turn left, flip it to white, move forward. That’s everything. No memory, no planning, no communication.

Run it for a hundred steps and you get a small symmetric pattern. Run it for a thousand and you get chaos — an asymmetric blob spreading in no particular direction. Run it for about eleven thousand steps and something unexpected happens: the ant starts building a diagonal highway, a repeating 104-step pattern that extends forever in the same direction. Every time. No matter what obstacles you place in its path, it eventually finds or constructs the highway.

Nobody has proven why this happens.

(define N 64)
(define dxs #(0 1 0 -1))
(define dys #(1 0 -1 0))
(define (grid-ref g x y) (vector-ref g (+ (* y N) x)))
(define (grid-flip g x y)            ; returns a NEW grid, threading state
  (let ((g2 (vector-copy g)))
    (vector-set! g2 (+ (* y N) x) (- 1 (grid-ref g x y)))
    g2))

(define (langton g x y dir steps)
  (if (zero? steps)
      (list x y dir)
      (let* ((cell (grid-ref g x y))
             (new-dir (modulo (+ dir (if (zero? cell) 1 3)) 4)))
        (langton (grid-flip g x y)
                 (+ x (vector-ref dxs new-dir))
                 (+ y (vector-ref dys new-dir))
                 new-dir (- steps 1)))))

(let ((r (langton (make-vector (* N N) 0) 32 32 0 50)))
  (display (string-append "after 50 steps: x=" (number->string (car r))
                          " y=" (number->string (cadr r))
                          " dir=" (number->string (caddr r))))
  (newline))

public class LangtonsAnt {
    static final int N = 64;
    static int[][] grid = new int[N][N];
    static int x = 32, y = 32, dir = 0;
    static final int[] dx = {0, 1, 0, -1};
    static final int[] dy = {1, 0, -1, 0};

    static void step() {
        int cell = grid[x][y];
        dir = (dir + (cell == 0 ? 1 : 3)) % 4;  // right if white, left if black
        grid[x][y] ^= 1;                        // mutate the cell in place
        x += dx[dir];
        y += dy[dir];
    }

    public static void main(String[] args) {
        for (int i = 0; i < 50; i++) step();
        System.out.println("after 50 steps: x=" + x + " y=" + y + " dir=" + dir);
    }
}

The Scheme version is recursive, threading state through each step. The Java version mutates — grid[x][y] ^= 1 flips between 0 and 1. Both produce identical results: chaos that self-organizes into order after roughly 10,000 iterations.

I keep thinking about that test tube. The queen in there is following her own two-rule program: tend eggs, conserve energy. No planning. No understanding of what a colony is. Yet in six months, if I don’t disturb her, there will be tunnels and chambers and a functioning society.

Langton’s Ant doesn’t explain ant colonies. But it demonstrates that the gap between simple rules and complex outcomes isn’t a metaphor — it’s a mathematical phenomenon. The highway emerges whether you believe in it or not.