Langton’s Ant

The ant starts out on the central square. Each square is assigned a shade, black or white (but unvisited squares are shown in grey in the pictures). The ant’s state at any moment is described by which square it is on and which direction it is facing. It then moves one square forward. If it lands on a white square, it turns right and paints that square black; otherwise it paints the square black and turns left.

These rules are very simple, but their consequences are not well understood. After a little experimenting, you can guess what probably always happens eventually, but as far as I know the natural conjecture has not been proven.

Refer to Mathematical Recreations in the July, 1994 issue of Scientific American.