Langton's Ant
A two-dimensional universal Turing machine running on a grid. Initially, simple rules generate completely chaotic and seemingly random behavior, but eventually, an emergent ordered structure—a "highway"—is reliably built.
The Rules
Langton's ant operates on a grid of cells. The classic rules (RL) are:
- At a white square, turn 90° right, flip the color of the square, and move forward one unit.
- At a black square, turn 90° left, flip the color of the square, and move forward one unit.
Generalized rules use a string of 'R' and 'L' instructions, dictating the turn direction for each color state sequentially, cycling back to the first color after the last.
Emergence
Despite the deterministic rules, the classic ant exhibits three distinct modes of behavior. First, a symmetric pattern is formed. Second, pseudo-random chaos dominates. Finally, around 10,000 steps, a stable "highway" pattern emerges, building indefinitely.