The cellular automaton Langton’s Ant follows just two simple commands, and in doing so moves in turn from symmetry to chaos to implacable order.
Cellular automata are a fascinating kind of abstract experiment that demonstrate how complex patterns and behaviour can emerge from simple rules and constraints. The most famous cellular automaton is Conway’s Game of Life, but today I wanted to highlight a different one: Langton’s Ant.
It begins, as many cellular automata do, with an infinite grid. Each square on this grid can either be coloured black or white. On that infinite grid, place a single ant. That ant has the power to switch squares between black and white, according to the following two rules:
- If the ant is standing on a white square, it turns right, toggles the square underneath it black, and then moves forward one square.
- If the ant is standing on a black square, it turns left, toggles the square underneath it white, and then moves forward one square.
And that’s it, that’s the complete setup. From these simple rules three distinct stages come out. First, the ant circles around and around and creates a nice little pattern of symmetrical loops. Then, the patterns disappear and the grid disappears into a chaotic mess. And finally, more than ten thousand steps in, the ant begins the creation of a straight pathway that shoots off in one direction…and never stops. From those two simple rules you get pattern, then chaos, then emergent order.
Why should we care? Well, it turns out that mathematicians, physicists, philosophers, and creators have a lot to unpack from the idea of cellular automata. In a deterministic universe, everything is a kind of cellular automaton, and matter, life, and thought are all complexity arising from a few simple rules. Langton’s ant is a microscopic demonstration of that behaviour. Flipping that around, because simple rules can lead to chaotic messes, computer programmers can use cellular automata to generate natural-looking terrain. (There are actually several clever tricks used to procedurally generate random landforms in video games, but that’s a post for another time.)