Prize: Fame and fortune!

(Plus a free book from whatever I have in stock.)

Due Date: March 15, 2011

The Science of Discworld talks about Langton's Ant. The idea is a tiny ant is sitting in the middle of a grid of squares that are either black or white. There are only three rules. During each round:

1. Turn:
   1. If the ant is on a white square, turn right.
   2. If the ant is on a black square, turn left.
2. Switch the color of the ant's current square.
3. Move forward one square.

The contest is to build a Langton's Ant simulator. Possible features:

• Start and stop the ant.
• Display the grid at different scales (in case the ant wanders far away).
• Save the current situation including the grid and the ant's position and direction.
• Reload a situation and run from there.
• Save an image of the grid.
• Run displaying the round number without showing the grid (for extra speed to run a lot of rounds).

The "standard" start position is an all white board. For extra credit, also allow the user to select a checkerboard or other interesting initial board patterns (random, white with a block of black, and so forth).

The ant shows three distinct types of behavior over time. To see the third type of behavior, you need to be able to run the ant for more than 10,000 rounds so be sure your program can run that long.

---

Discussion

Langton's Ant shows three distinct "behaviors." Initially it seems to move with a purpose, building itself a little nest. After a while, the ant makes a bigger and bigger nest and gives the nest a rather chaotic structure. After about 10,000 moves, the ant starts building a "highway" moving away from the nest.

Simple Rules, Complex Behavior

One moral of Langton's Ant is that a small set of simple rules can lead to apparently complex behavior. This has some interesting philosophical consequences. The world around us is filled with apparently complex processes and behaviors. It is possible that at least some of these are due to very simple "rules" even if those rules are not easy to see. A colony of real ants shows complex behaviors but an ant's brain cannot be very complex. Each ant must operate on a relatively simple set of "rules" yet somehow together they form a complex society.

Similarly you can build a quite realistic model of weather behavior using a few simple rules. Weather is not only complex but it is also chaotic so predicting its behavior is extremely difficult.

Just because something is governed by a simple set of rules doesn't mean you can easily discover those rules. Looking at Langton's Ant from any distance, it would be hard to deduce its three rules of movement.

This also doesn't mean that complex behavior cannot also come from complex rules. Even apparently simple behavior can come from complex rules.

The Halting Problem

Langton's Ant also demonstrates an important computer science concept: the halting problem. Suppose you have a computer program (like the Ant's "program"). The problem is to determine whether the program eventually halts. Knowing the Langton's Ant rules, you probably would not guess that the ant would eventually end up building a "highway" away from its "nest." Even if you ran the ant simulation, you would probably not suspect that result initially. If you got tired of watching the ant, you might stop well before the 10,000 moves needed to see the highway develop.

The halting problem applies to a more general class of programs and there are several programs that pose quite a puzzle. For example, you can build a program that evaluates logical expressions and determines whether they are true. Unfortunately the algorithm doesn't necessarily ever halt. If the logical statement is true, the program will eventually find out. If it is not true, however, the program may run forever. So the question is, after 10,000 steps, do you assume the statement is false? Or do you run 100,000 steps? 1,000,000? It's easy to tell that some programs eventually halt (for example, Windows), but for others there is no way to be sure until they actually do halt.

Computability theory deals with this and other problems that ask, "Can something be computed?" The related field complexity theory asks, "How long does it take to compute something?" These are two of my favorite fields of computer science research.

Turing Machines

If you enjoyed working with Langton's Ant, you may also be interested in Turing machines. A Turing machine is a hypothetical computer with rules about as simple as those used by Langton's Ant. One simple form of machine reads an infinite tape. Each cell in the tape contains a 0 or 1. When it reads a value, the machine checks its rules to see what to do. The rules tell the machine whether to make the cell a 0 or 1, whether to move left or right on the tape, and what state to move into next. The states determine which rules apply at any given point. Other kinds of Turing machines use "machines" with features such as multiple tape heads and multiple tapes.

These simple machines are extremely powerful and with the right set of rules they can perform addition, multiplication, exponentiation, and all sorts of other mathematical operations (if you like this stuff, it's fun to build a Turing machine simulator and then watch it run programs for exponentiation). With a little work, you can show that some kinds of Turing machines are just as powerful as a Pentium 4. Turing machines let you study other kinds of computability issues.