Langton's Ant - from simple rules to complex behavior

The following system is created using a very simple set of rules:

1. Let's assume an infinite 2D grid world. Each grid cell can be either black or white.
   
2. For simplicity, all grid cells are white at the beginning.
   
3. There is an ant, which can move up to four directions (N,E,S,W).
   
4. Whenever the ant enters a white field, it toggles the grid color and performs a clockwise (right) turn.
   
5. Whenever the ant enters a black field, it toggles the grid color and performs a counter-clockwise (left) turn.
   

You got the rules? Let's play! Get yourself some squared paper, a pencil and a rubber and start drawing. Or, if you are lazy, just use the Java applet below. Unfortunately I failed in simulating the infinite grid, so the simulation reverses whenever the ant leaves the system boundary, but this does not make a difference for the first 10000 iterations. You may use the mousewheel to scroll and modify the simulation speed in order to investigate what the ant is up to.


Despite the simple rules, the ant is following an interesting and unexpected path. This relates to what Carlos Gershenson has pointed out in his blog: a deterministic system does not necessarily mean that it is predictable. A system is deterministic if no randomness is involved in the development of future states of the system. Thus, given a particular starting condition, the system will always develop its future states in the same way. The real physical world, considering the randomness in quantum effects, is not deterministic. But the simulated ant in our example is. On the other hand, prediction means the ability to make a forecast of a system's state (either qualitatively or quantitatively). These two terms represent different concepts and should not be mixed up.

In our deterministic ant system, it is not possible to predict the behavior by looking at the rules unless you have tried out the simulation beforehand. Although we have just one agent, we face a complex system, since the agent is interacting with every single cell it arrives. And each move changes the cell and orientation, thus creates new information. The interesting and unexpected thing is what the ant is doing after roughly 10200 steps. Until then the movement is chaotic. But subsequently, the ant produces a "highway" by walking away to the south-east in repeated sequences of 104 steps. From that point on, the future system states can be predicted for all future states.
If you liked this, check out the work of Propp et al. on Langton's ants with multiple grid colors. They present a three-color model where it is not known if the ant will ever enter a stage producing a predictable highway. So far on deterministic models - in your face, predictability!

• Langton's ant@Wikipedia
  
• Gale, D.; J. Propp, S. Sutherland, S.Troubetzkoy, Further Travels with My Ant. Mathematical Entertainments column, Mathematical Intelligencer 17: 48–56, 1995.
  
• Carlos Gershenson, Determinism != Predictability, Complexes Blog, September, 2010