Langton's Ant

1. The two rules

Christopher Langton introduced the ant in 1986 as a thought experiment in artificial life. The setting is a two-dimensional grid where every cell is either white (off) or black (on). The ant occupies one cell and faces one of four cardinal directions — North, East, South, West.

At each step the ant applies two rules, in order:

1. Turn: if the current cell is white, turn 90° right (clockwise); if the current cell is black, turn 90° left (counter-clockwise).
2. Flip and move: flip the colour of the current cell (white ↔ black), then move forward one step into the next cell.

That is the complete specification. No extra state is stored. The ant has no memory of previous positions; it reacts only to the cell it currently stands on. Everything that follows — the initial chaos, the eventual highway — emerges from these three lines.

2. Three behavioural phases

Starting from a completely white grid, Langton's Ant passes through three distinct phases as step count increases. The transitions are sharp and well-studied, though not fully proven for all initial conditions.

The onset of the highway is not at a fixed step number — it depends on the exact configuration of black cells built during the chaotic phase. On an all-white grid, the highway typically starts around step 9,978 and the ant moves in the direction (−2, 2) or a rotated equivalent.

Sensitive dependence on initial conditions?

Despite superficial similarity to chaos, Langton's Ant is not chaotic in the dynamical-systems sense. It is deterministic and its state space is discrete. However, two initial configurations that differ by a single flipped cell can lead to highways of completely different orientations or to continued wandering for much longer — a form of sensitivity that is discrete rather than continuous.

3. The highway: proof and mystery

The highway conjecture states: starting from any finite initial configuration of black cells on an otherwise white infinite grid, Langton's Ant will eventually build a highway.

As of 2026, the conjecture remains unproven — one of the most surprising open problems in the study of simple deterministic systems. Extensive computer search has not found any initial configuration that fails to produce a highway, but no general proof exists.

What is known for the all-white initial condition:

• The highway is a period-104 cycle of moves, producing a net displacement of (2, −2) per period (or rotational equivalents).
• The highway "footprint" — the set of cells flipped during one period — consists of exactly 26 black cells arranged in a repeating tile.
• The ant moves diagonally at exactly 2/104 ≈ 0.0192 cells per step averaged over one period.
• The highway direction is determined by the chirality of the configuration at the moment the ant first locks in; on a blank grid, this is always the same due to the symmetry of the initial phase.

Why does the highway appear?

There is no complete mechanistic explanation. The best current understanding is that the chaotic phase gradually builds up regions of black cells that inadvertently "channel" the ant into a highway-compatible local configuration. Once the ant encounters such a configuration, the period-104 cycle self-reinforces because the cells it flips exactly recreate the required local state 104 steps later.

4. Symmetry and initial conditions

The all-white initial condition has fourfold rotational symmetry, but the ant itself breaks this symmetry at step 1 by turning right. As a result, the final highway direction is determined by this first-step symmetry breaking — it always emerges in the same orientation for the same starting direction.

Initial configurations with black cells can break the symmetry in arbitrary ways, leading to highways in any of the four diagonal directions, or delaying the highway onset to hundreds of thousands of steps.

* Multi-ant systems create entirely different dynamics and are not covered by the standard highway conjecture.

Mirror symmetry

Reversing the rules (RL → LR) simply mirrors the entire trajectory. An LR ant on an all-white grid produces the same pattern as an RL ant reflected about the y-axis, and its highway runs in the opposite diagonal direction.

5. Turmites: generalising the ant

A Turmite (coined by Rudy Rucker, combining "Turing" and "termite") generalises Langton's Ant by allowing:

• More than 2 cell colours (k colours)
• More than 1 ant internal state (s states)
• Rules encoded as a transition table: (current_state, cell_colour) → (new_state, new_colour, turn)

The original Langton's Ant is the simplest Turmite: k = 2 colours, s = 1 internal state. Its transition table is:

With k colours and s states, a Turmite has s × k rules — the number of distinct Turmites with s = 1 and k colours is 4ᵏ (four possible turn directions per rule) × kᵏ (k possible new colours per rule). Even for k = 3 (three colours), this gives 10,000+ distinct ants, most exhibiting radically different emergent behaviour.

6. Rule notation and a zoo of ants

Multi-colour Langton ants (single internal state) are described by a string of letters where each letter describes what to do on a cell of that colour:

• R — turn right 90°
• L — turn left 90°
• U — turn around 180° (U-turn)
• N — go straight (no turn)

The cell colour is incremented by 1 mod k after each step (cycling through the k colours in order), and the letter at position i of the rule string describes the turn on colour i.

Notable behaviours

7. Computational universality

Turmites with multiple internal states are known to be Turing complete — they can simulate any computation given a suitable initial tape (grid configuration). The simplest known Turing-complete Turmite has 2 internal states and 2 colours, placing Langton-style machines at the boundary of computational universality.

The original single-state 2-colour Langton's Ant (RL) is not known to be Turing complete. Its trajectory eventually becomes periodic (the highway), which would rule out universal computation — a universal machine must be able to run for an unbounded number of distinct steps without cycling. However, the highway conjecture is unproven, so the question of universality for the standard ant remains technically open.

Relation to one-dimensional cellular automata

Langton's Ant is formally a two-dimensional Turing machine with a stationary head that moves on a 2D tape. It differs from Wolfram's 1D elementary cellular automata in that space-time is not the relevant structure — instead, the ant traces a path through a 2D environment it modifies as it goes.

Despite the two-dimensionality, Langton's Ant is informationally sparse: the complete state at any step is just the ant's (x, y) position, direction, and the full grid configuration. The grid is the "memory", and the ant is the "processor".

8. JavaScript implementation

// Langton's Ant — compact canvas implementation
// Supports arbitrary rule strings like "RL", "RLLR", "LRRRRRLLR"

const CELL_SIZE = 3;      // pixels per cell
const GRID_W    = 300;    // grid width in cells
const GRID_H    = 300;    // grid height in cells
const RULE      = "RL";   // rule string — one letter per colour state

// Colour palette: one colour per state
const PALETTE = ["#1e1e2e", "#f59e0b", "#6366f1", "#10b981", "#ef4444", "#a78bfa"];
const NUM_STATES = RULE.length;

// Grid: 2D array of integer colour states [0..NUM_STATES-1]
const grid = new Array(GRID_H).fill(null).map(() => new Uint8Array(GRID_W));

// Ant state
let ax = Math.floor(GRID_W / 2);   // ant x
let ay = Math.floor(GRID_H / 2);   // ant y
let dir = 0;  // 0=North, 1=East, 2=South, 3=West

const DX = [ 0, 1,  0, -1];  // East offset per direction
const DY = [-1, 0,  1,  0];  // South offset (Y grows down)

function step(n = 1) {
  for (let i = 0; i < n; i++) {
    const state = grid[ay][ax];
    const rule  = RULE[state];

    // Turn
    if      (rule === 'R') dir = (dir + 1) & 3;
    else if (rule === 'L') dir = (dir + 3) & 3;   // +3 mod 4 = -1
    else if (rule === 'U') dir = (dir + 2) & 3;
    // 'N' = no turn

    // Flip colour (cycle to next state)
    grid[ay][ax] = (state + 1) % NUM_STATES;

    // Move forward
    ax = (ax + DX[dir] + GRID_W) % GRID_W;
    ay = (ay + DY[dir] + GRID_H) % GRID_H;
  }
}

function draw(ctx) {
  for (let y = 0; y < GRID_H; y++) {
    for (let x = 0; x < GRID_W; x++) {
      const s = grid[y][x];
      if (s === 0) continue;   // skip background cells for speed
      ctx.fillStyle = PALETTE[s % PALETTE.length];
      ctx.fillRect(x * CELL_SIZE, y * CELL_SIZE, CELL_SIZE, CELL_SIZE);
    }
  }
  // Draw ant
  ctx.fillStyle = "#ffffff";
  ctx.fillRect(ax * CELL_SIZE, ay * CELL_SIZE, CELL_SIZE, CELL_SIZE);
}

// Animation loop
function setup(canvas) {
  const ctx = canvas.getContext("2d");
  canvas.width  = GRID_W * CELL_SIZE;
  canvas.height = GRID_H * CELL_SIZE;

  function frame() {
    step(50);                          // 50 ant steps per animation frame
    ctx.clearRect(0, 0, canvas.width, canvas.height);
    draw(ctx);
    requestAnimationFrame(frame);
  }
  requestAnimationFrame(frame);
}
        

Performance notes

At 50 steps per frame and 60 FPS, the simulation runs at 3,000 ant steps per second — enough to reach the highway onset (~10,000 steps) in about 3 seconds of real time. The skip background optimisation in the draw loop avoids iterating over the ≈ 83,000 white cells at every frame; only cells with non-zero state (black cells) need to be drawn.

For larger grids or higher step counts, consider using an ImageData pixel array instead of individual fillRect calls: write RGBA values directly into a typed array and batch-commit with putImageData — typically 10–50× faster than per-cell rectangle drawing.

Wrapping vs infinite grid

The implementation above wraps at grid boundaries (toroidal topology). On a toroidal grid, the highway will eventually wrap around and the ant may re-enter its own trail, producing different long-term behaviour. For faithful simulation of the infinite-grid conjecture, use an expanding hash map (JavaScript Map with string keys "x,y") that grows as the ant visits new cells.