What Does an Ant Do with Two Simple Rules?

Be the ant

Now be the ant yourself: choose each turn, and the page paints and steps.

• a.Do the first 4 steps. What shape have you made, and where is the ant?
• b.Step 5 is the first time the ant lands on a black square. What happens to that square?
• c.Press Do the rest for me. The page stops at step 184. Turn your phone (or your head) upside down: what do you notice?

Watch the mess, then the highway

Go back to Run the ant at the top. Press ↺, choose Fast, and press Run.

• a.Up to about step 500 the shapes are small and neat. What happens after that?
• b.Keep watching (Very fast helps). When does the Highway readout say it has started? Which way does the highway go?
• c.What happens when the highway reaches the edge of the page?

Start on a different page

Now choose Square (a 3 × 3 black square under the ant before it starts) and press Run. Then choose Scattered: half of a 10 × 10 patch round the ant is black, at random. Press Scattered again for a new random patch each time.

Two rules, but no shortcut

Why can’t we look at the tiny rules and say what the ant will do at step 10,000? The ant’s turn depends on the color of its square, and that color depends on every earlier visit, which depends on the steps before that, all the way back to step 1. Nobody has found a formula that jumps to step 10,000. The only known way to find out what happens is to do every step, and that is exactly what a computer is good at: 10,000 steps take your phone a fraction of a second.

A program that applies simple rules over and over, step by step, is a simulation. When many small parts following simple rules make a big pattern that none of the rules mentions, it is called emergence. Termites build towering mounds this way, and a flock of birds turns together, with no leader telling each bird what to do.

The highway, close up

The highway isn’t a new rule: the ant still follows the same two. But from step 9,978 the squares in front of it happen to be set up so that the ant does exactly the same 104 steps over and over. Each time round it moves 2 squares sideways and 2 squares up or down, so the highway runs diagonally, and leaves 12 more black squares behind it. Because the squares in front of it are always white, nothing can ever break the repeat: on an endless page, the ant keeps going forever. Your Step 3 program finds all these numbers by itself.

What has been proved, and what hasn’t

Mathematicians have proved one thing for certain: the ant can never stay inside a box forever. Whatever pattern of black squares it starts on (as long as it is a finite patch), it always gets out of any box you draw, however big. The mathematicians Leonid Bunimovich and Serge Troubetzkoy published a proof in 1992. Two articles soon after, one of them Ian Stewart’s 1994 puzzle column in Scientific American, credited it to the physicists E. G. D. Cohen and X. P. Kong, so you may see it called the Cohen–Kong theorem.

But that is not the same as proving that the ant always builds a highway. Every start anyone has tried has ended in the same highway, sooner or later. Nobody has proved that every start must. Some pattern might make the ant wander in a mess forever. As of 2026, this is still an open question, one that a student can understand completely but nobody has yet answered.

With blocks: the ant’s compass

The ant needs to know which way it is facing. Number the four ways: 0 up, 1 right, 2 down, 3 left. A right turn adds 1. Going past 3 must bring you back to 0, so take the remainder of the sum divided by 4. A left turn is the same as three right turns, so it adds 3 (then the remainder again).

In Python (from Grade 8)

Step 1: the two rules

The paper is a list of lists: grid is a list of 21 rows, and each row is a list of 21 numbers, 0 for white and 1 for black. grid[y][x] is the square in row y, column x. [0] * 21 makes a row of twenty-one 0s, and grid.append(…) adds a row to the end of the list.

The two lists STEP_X and STEP_Y say how a step forward changes the ant’s column and row for each of the four ways it can face (rows count downward, so up is −1).

from pixels import show_grid SIZE = 21grid = []for row in range(SIZE):    grid.append([0] * SIZE)      # a row of white squares x = 10                           # the ant starts in the middle,y = 10facing = 0                       # facing up (0 up, 1 right, 2 down, 3 left)STEP_X = [0, 1, 0, -1]STEP_Y = [-1, 0, 1, 0] for step in range(184):    if grid[y][x] == 0:          # white: turn right, paint it black        facing = (facing + 1) % 4        grid[y][x] = 1    else:                        # black: turn left, paint it white        facing = (facing + 3) % 4        grid[y][x] = 0    x = x + STEP_X[facing]       # step forward    y = y + STEP_Y[facing] print('After 184 steps the ant is at column', x, 'row', y)grid[y][x] = 2                   # mark the ant, to see it in the pictureshow_grid(grid, ['white', 'black', 'red'])

After 184 steps the ant is at column 10 row 10

Picture

show_grid is part of the page’s own pixels module: it colors one square for each number, 0 white, 1 black and 2 red. (On your own computer you would draw it with a library such as Pillow.)

Change 184 to 368, then 472. Then try 600: the neat shapes are over. (At 1,000 Python stops with an IndexError: the ant has walked off this small page. Step 2 gives it a bigger one.)

Step 2: twelve thousand steps, as a film

Now a bigger page, 120 squares across, and a picture after every 500 steps, played as a film by show_frames. Two things are new. The ant must stop when it reaches the edge, so the loop is a while that keeps going only while the ant is on the page (0 <= x < SIZE means x is at least 0 and less than SIZE). And each frame must be a copy of the grid (row[:] copies a row): if the film kept the grid itself, every frame would show the last picture.

from pixels import show_frames SIZE = 120grid = []for row in range(SIZE):    grid.append([0] * SIZE)x = SIZE // 2y = SIZE // 2facing = 0STEP_X = [0, 1, 0, -1]STEP_Y = [-1, 0, 1, 0] frames = []steps = 0while 0 <= x < SIZE and 0 <= y < SIZE:    if grid[y][x] == 0:        facing = (facing + 1) % 4        grid[y][x] = 1    else:        facing = (facing + 3) % 4        grid[y][x] = 0    x = x + STEP_X[facing]    y = y + STEP_Y[facing]    steps = steps + 1    if steps % 500 == 0:         # every 500 steps, keep a copy of the page        frame = []        for row in grid:            frame.append(row[:])        frames.append(frame) print('The ant walked off the page after', steps, 'steps.')show_frames(frames, ['white', 'black'])

The ant walked off the page after 12189 steps.

Picture

Press Play under the picture, or move the slider. Find the frame where the highway first shows.

Step 3: find the highway

How can a program find the highway without being told what it looks like? Look at the ant’s turns: on the highway its list of turns, R and L, repeats. A mess doesn’t.

The ant from Step 2, as a function, is in a file the page keeps for you, langton.py. run_ant(grid, steps) runs the ant on grid and gives back the list of its turns, one 'R' or 'L' for each step.

The program asks the turns three questions. How long is the repeat? Try p = 1, 2, 3… until the last 520 turns each match the turn p before. Where does it begin? Walk back from the end while each turn matches the one p later. What happens in one repeat? Every right turn paints a square black, every left turn one white.

from langton import new_grid, run_ant def repeats(turns, p):    # is each of the last 520 turns the same as the turn p before it?    for k in range(len(turns) - 520, len(turns)):        if turns[k] != turns[k - p]:            return False    return True grid = new_grid(120)turns = run_ant(grid, 20000)print(len(turns), 'steps on the page') p = 1while not repeats(turns, p):    p = p + 1print('The turns repeat every', p, 'steps') k = len(turns) - p - 1while turns[k] == turns[k + p]:    k = k - 1# turns[k] is the last turn that doesn't repeat; Python counts from 0,# so the first repeating turn, turns[k + 1], is step k + 2print('The highway starts at step', k + 2) last = turns[len(turns) - p:]print('In each repeat:', last.count('R'), 'right turns and', last.count('L'), 'left turns')print('So each repeat leaves', last.count('R') - last.count('L'), 'more black squares')

12189 steps on the pageThe turns repeat every 104 stepsThe highway starts at step 9978In each repeat: 58 right turns and 46 left turnsSo each repeat leaves 12 more black squares

turns.count('R') counts the 'R's in a list, and turns[len(turns) - p:] is its last p items.

Step 4: a hundred different starts

Does every start end in a highway? Your program can’t try them all (there are far too many), but it can try a hundred. random.seed(n) makes the same random patch every time for the same n, so you can come back to an interesting one.

import randomfrom langton import new_grid, run_ant, highway_start found = 0soonest = 100000latest = 0for n in range(1, 101):    random.seed(n)    grid = new_grid(120)    for y in range(55, 65):              # a 10 x 10 patch round the middle,        for x in range(55, 65):            if random.random() < 0.5:    # each square black half the time                grid[y][x] = 1    turns = run_ant(grid, 60000)    start = highway_start(turns, 104)    if start != None:        found = found + 1        if start < soonest:            soonest = start            soonest_n = n        if start > latest:            latest = start            latest_n = n print(found, 'of 100 starts built the highway')print('Soonest: step', soonest, 'with patch', soonest_n)print('Latest: step', latest, 'with patch', latest_n)

100 of 100 starts built the highwaySoonest: step 357 with patch 32Latest: step 33649 with patch 12

• On a white page, Langton’s ant makes a mess for 9,977 steps, and from step 9,978 it builds the highway.
• On the highway the ant repeats the same 104 steps: 58 right turns and 46 left, so each repeat leaves 12 more black squares and moves it 2 squares diagonally.
• Your hundred random starts all built the same highway, some after 357 steps, one after 33,649.

Two rules, and a program of twenty lines, produced something nobody could predict by looking at the rules, and that the best mathematicians still can’t prove always happens. Complicated behavior doesn’t need complicated rules: that idea runs through science, from weather to traffic to living things.

More colors. Give the paper more colors, each with its own turn, in order: on color 1 the ant turns as the first letter says, and the square moves on to the next color. Langton’s ant is RL. Try the others.

It has been proved that a rule made of pairs, like LLRR (LL then RR), makes a shape that looks the same on both sides again and again as it grows. With RLR, nobody knows whether it ever builds a highway.

Run it backwards. The ant can be run backwards exactly: from the picture at step 11,000 you can get all the way back to a white page. Challenge ★★★ asks you to work out how.

The open question. Does every finite starting pattern end in the highway? Your hundred tries say yes; a proof would say why. Nobody has one yet.

★ Which way does it face? (blocks)

Finish the compass so that, after the 6 squares, it says which way the ant faces as a word: up, right, down or left (and nothing else). Then press Test. Which words does it never say?

★★ How big is the mess? (Python, from Grade 8)

Write mess_size(steps) that runs Langton’s ant for steps steps on an endless white page and gives back the width and height of the smallest box that holds every black square, as a list [width, height] ([0, 0] if there are none).

def mess_size(steps):    # run the ant `steps` steps; the box round its black squares    return [0, 0] print(mess_size(4))

★★★ Run it backwards (Python, from Grade 8)

Write step_back(black, x, y, facing): the ant is at column x, row y, facing facing (0 up, 1 right, 2 down, 3 left, rows counting down), on a page whose black squares are listed in black as [column, row] pairs. Give back where everything was one step earlier, as [black, x, y, facing], with the black squares in order (sorted(black)).

def step_back(black, x, y, facing):    # undo one step of the ant    return [sorted(black), x, y, facing] print(step_back([[0, 0]], 1, 0, 1))

• Grade 6, Programming with Blocks: the turtle that turns and steps, the ant’s cousin, and loops that do it again.
• Grade 7, Variables and Choices: if/else, which the ant uses at every step.
• Grade 8, Decisions and Loops in Python: while loops that stop when something becomes false, as the ant stops at the edge.
• How far does a wandering ant get? An ant that steps at random instead, and why it gets only about 10 steps away in 100.
• Can a robot get out of any maze? Another simple rule, followed step by step, that gets somewhere surprising.