Langton's Ant

October 14th, 2017

Langton's ant is a famous cellular automaton invented by Chris Langton in the 80s which exhibits some very interesting behavior. The rules for this CA are very simple: the ant lives on an infinite grid and decides whether to turn left or right by looking at the color of the cell it is currently on. Traditionally, every cell is either black or white, and if the ant is on a white cell, it turns the cell black and turns right. If it lands on a black cell, it turns that cell white and turns left.

As with all interesting cellular automata, the fascinating part of this is that the behavior of the ant is fully deterministic, and yet still seems random and unpredictable. For example, using the two simple rules above, the ant produces a sort of symmetric, but generally unpredictable behavior for roughly 10,000 steps. And then suddenly produces a perfectly regular pattern forever.

But this lends itself to a nice generalization. Suppose we have three colors. If it lands on color one it changes it to color two, and turns left. If it lands on color two, it changes it to color three, and turns right. Then if it lands on color three, it changes it to color one, and turns left. So we could describe this rule more concisely by calling it LRL. Many of these produce similarly unpredictable behavior. Some, like LLL will simply cycle forever. Others, like RLL will settle into a simple cycle after only 150 steps! In this context, the original rules can be written as RL.

Initially, the whole grid is just a single color, but we could make this a bit more complicated by allowing the board to be filled with various colors. If we use just two colors, we can think of cells in the grid as being on or off. With this interpretation of the grid, it was proven in 2000 that using only the simple rule RL originally proposed by Langton, the behavior of the ant is turing complete! In other words, we could strategically turn on cells in this grid to simulate langston's ant using langstons's ant! of course, one step in the simulated ant would probably correspond to a million steps for our ant.

Some smart people who went on to create the most 1995 company website ever wrote a paper about these generalized Langton's ants. It turns out that if we have a rule like RRLL or RLLRRLLR, what they called the "even run-length property", we get interesting symmetry. Specifically, if we interpret L as 1 and R as 0, we can view the rules as binary numbers, and the rules which produce interesting bilateral symmetry are the rules which are divisible by 3!

Unfortunately, I made my ant live on a torus, so their results don't quite apply... Oh well, it looks pretty!