Langton’s Ant

http://commons.wikimedia.org/wiki/File:LangtonsAntAnimated.gif

Set an ant down on a grid of squares and ask it to follow two rules:

  1. If you find yourself on a white square, turn 90° right, change the color of the square to black, and move forward one unit.
  2. If you find yourself on a black square, turn 90° left, change the color of the square to white, and move forward one unit.

That’s it. At first the ant will seem to mill around uncertainly, as above, producing an irregular jumble of black and white squares. But after about 10,000 steps it will start to build a “highway,” following a repeating loop of 104 steps that unfolds forever (below). Computer scientist Chris Langton discovered the phenomenon in 1986.

Will this happen even if some of the starting squares are black? So far the answer appears to be yes — in every initial configuration that’s been tested, the ant eventually produces a highway. If there’s an exception, no one has found it yet.