Langton's ant

Did You Know?

• A further extension considers multiple states of the Turing machine, as if the ant itself has a color that can change; these ants are called turmites.
• Common turmite behaviors include the production of highways, chaotic growth, and spiral growth.
• Multiple turmites can coexist as long as there is a rule defining what happens when they meet.

Rules

Squares on a plane are colored either black or white. One square is identified as the ant, which can travel in any of the four cardinal directions. At a white square, the ant turns 90° clockwise, flips the color of the square, and moves forward one unit. At a black square, it turns 90° counter-clockwise, flips the color, and moves forward one unit. The system can also be described as a cellular automaton where the ant square has one of eight colors encoding its state and direction.

Modes of behavior

Starting on a completely white grid, three distinct modes of behavior appear. During the first few hundred moves, simple and often symmetric patterns form. After a few hundred moves, a large irregular pattern emerges and the ant traces a pseudo-random path until around 10,000 steps. Finally, the ant begins building a recurrent highway pattern of 104 steps that repeats indefinitely. All finite initial configurations tested eventually converge to this highway, suggesting it is an attractor, though this has not been proven for all configurations. The ant's trajectory is always unbounded regardless of initial configuration, a result known as the Cohen-Kong theorem.

Extension to multiple colors

Greg Turk and Jim Propp extended Langton's ant to use more than two colors, modified in a cyclic fashion. A naming scheme uses letters L or R to indicate left or right turns for each successive color; Langton's ant is named RL. Some extended ants produce patterns that become symmetric repeatedly, such as RLLR. A sufficient condition for this symmetry is that the ant's name, as a cyclic list, consists of consecutive pairs of identical letters (LL or RR); the proof involves Truchet tiles. On a hexagonal grid, up to six rotations are possible, notated as N, R1, R2, U, L2, and L1.

Extension to multiple ants

When multiple Langton's ants share a two-dimensional grid, their encounters produce complex, higher-order patterns and organized structures. How these interactions are modeled heavily influences the simulation's outcome. Ed Pegg, Jr. explored ants that can turn left or right, splitting into two or annihilating each other upon meeting.