Langton's Ant

A 4-state two-dimensional Turing machine invented in the 1980s. The ant starts out on a grid containing black and white cells, and then follows the following set of rules.

1. If the ant is on a black square, it turns right and moves forward one unit.

2. If the ant is on a white square, it turns left and moves forward one unit.

3. When the ant leaves a square, it inverts the color.

When the ant is started on an empty grid, it eventually builds a "highway" that is a series of 104 steps that repeat indefinitely, each time displacing the ant two pixels vertically and horizontally. The plots above show the ant starting from a completely white grid after 386 (left figure) and (right figure) steps. In the right figure, the highway is being constructed towards the lower right-hand corner. The fact that the ant's path is unbounded is guaranteed by the Cohen-Kung theorem. It is believed that no matter what initial pattern the ant is started on, it will eventually build a highway (although it might in principle take an extremely long time to reach this point). This would appear to follow naturally from the fact that Langton's ant is reversible, although it remains formally unproved (Beermann and Van Foeken).