## Langton's Ant:Some Lessons in Emergence and Understanding(under development, Paul Grobstein and Panama Geer)

"The world is so full of a number of things,
I'm sure we should all be as happy as ...
Robert Lous Stevenson (1850-1894)

And yet, one can't help but wonder a bit. Where did all those things COME from? Are there really so many things, or just a lot of different combinations of a few things? And how come its these PARTICULAR things, and not some other, different things?

"Langton's ant" is one of those things in the world, a fun thing to play with and enjoy (click here and it will appear in a separate window). And we know a bit about where this particular thing came from ... from the mind of a man named John Langton. And what's interesting about that is that "Langton's ant" is a relatively NEW thing in the world, so it serves to show that the particular things we see in the world at any given time are not the ONLY things that can be here.

But "Langton's ant" is even more than that. It gives us a way to think about some of the other questions we were wondering about as well. And, in doing that, it raises some interesting new questions. So ... let's play, and see what we can find.

The first thing to do is to click on the "setup" button. The black field turns greenish white, and a red dot appears in the center. That red dot is the ant. Now click on the "go continuously" button and the ant will move. As it does, some places its been will turn black. Keep an eye on the ant for a while.

created with NetLogo

Directions

(1) Click "setup" to initialize the applet.

(2) Click "go" to begin the applet.

(3) Click "go" again to stop the applet.

The speed can be adjusted at any time by moving the slider on the speed bar.

A square can be colored black at location (x,y) by clicking "make square (x,y) black". The values x and y are determined by the sliders x and y.

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.

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,

[2] "Mathematical Recreations: The Ultimate in Anty-Particles," Ian Stewart, Scientific American, July 1994, P. 104-107.