Documentation

This demonstration is often referred to as Langton's Ant, after its creator Chris Langton. The red square on the grid represents an ant. Initially, the ant is resting at the center of a grid of squares of one color. Imagine rectangular coordinate axes (x-axis and y-axis) imposed on the grid. This center grid sqare is denoted by the coordinates (x,y)=(0,0). The ant is given an initial direction, in this case towards the top of the screen, or in the positive y direction, which we will call north. However, the ant could also initially face east (positive x direction), west (negative x direction), or south (negative y direction). At each time step the ant follows rules (1) - (3).

(1) Take one step forward.

(2) If the ant is now standing on a green square, then paint it black and turn right 90 degrees.

(3) If the ant is now standing on a black square, then paint it green and turn left 90 degrees.

In the original statement of the problem the ant was on an infinite grid. This grid is a torus. Thus, when the ant reaches the edge of the grid it comes back on the grid on the opposite side.

Notice that the rules that govern the behavior of the ant are quite simple. Observe that in the first few hundred steps the ant "keeps returning to the central square, leaving behind it a series of rather symmetrical patterns."[2] After this, the pattern that the ant leaves appears very chaotic and this pattern continues until about the 10,000 time step. Up until this point there does not appear to be any organization in the pattern. Then, suddenly a very organized linear shape emerges from the seeminly chaotic pattern. This linear shape was first discovered by Joames Propp of MIT and was called a "highway."

Is there any way to predict that given the rules stated above, the ant will form a highway? Many investigations into this phenomenon have been done. However, so far, there is no formal proof to predict that the ant will form this highway.

Some questions to think about.

When does the highway begin formation?

Is it possible to form the highway sooner by making some cells black initially?

The ant repeatedly follows a particular sequence of steps to form the highway. How long is that sequence?

How does the size of the inital grid play a role in the formation of the highway?

For further information on Langton's Ant:

[1] "The Computational Beauty of Nature," by G. Flake, p. 264-270,