Langton's Ant is cellular automata in the planethat operates under very simple rules yet produces results which are seemingly unpredictable when the rules are changed slightly.

Langton's Ant
Imagine you are an ant in a grid of large squares in the plane with eachsquare you see colored black. Now as you are an ant, your mindless task is to do this:
  1. Change the color of the square you are standing on- (if the square is black change it to red and if it is red change it to black)
  2. Now Walk Forward to the square in front of you
  3. Look at the color of the square you are standing on. If it black turn Left and if it red turn Right by 90 degrees.
  4. Return to step 1.
  These may seem like very simple rules, but it isn't obvious what theresult will be(except you can probably figure out that the result is shown in the image to the right). In this case what ends up happening is the ant wanders arround chaotically for a while and then seens to organize itself and start moving a repeating pattern trailing off to the upper left. Forming a repeating pattern in this way has been called a highway.

This kind of ant can be generalized as follows: Choose n colors (force the first to be black). Then for each color decide whether you want the ant to turn left or right when he lands on a square of that color. Then the ant repeatedly increments the color of the square he is on (modulo n) then walks to the square in front of him, looks at the color of the square he is on and then turns the direction you decided corresponding to that color. There are several questions you could ask about such an ant such as:
  • Which ants eventually form a highway?
  • Which ants visit each square at least once?
  • Are there ants which produce symmetric patterns for all time?

As far as I know the answer to each of these questions is unknown. I have created a applet to demonstrate the outcome of this cellular automata with 16 or fewer colors.