C. G. Langton [Physica D 22, 120-149 (1986)] invented an amazingly simple computer automaton, which is governed by the following rules: Begin with a large grid of squares that are all white. The ant starts on the central square of the grid. It moves one square to the east and looks at the color of the square on which it lands. If it lands on a white square, it paints it black and turns 90o to the right. If it lands on a black square, it paints it white and turns 90o to the left. If the ant runs off the edge of the screen, it re-enters at the opposite edge (i.e., the boundary conditions are periodic). The ant follows these same simple rules forever.
This algorithm has been implemented in BASIC with source
and (DOS) object code provided. The program
differs slightly from the rules above in that rather than using black,
one of eight colors is chosen according to whether the previous turn was
to the right or left and which of the four directions the ant moved in
that step. This change produces a more colorful display. Output
from the program after 10 million iterations is shown below:
This system is ripe for exploration. One could calculate the Lyapunov
exponent and look at effects of grid size and boundary conditions.
One could start with more than one ant. The region could have a non-rectangular
shape. There could be various obstacles (rocks) that the ant encounters.
Other ways to generalize the calculation have also been
suggested.