With the advent of computers and their use in simulation has come the need to model complex interactions. One of the ways of doing this is to consider all interacting entities in a system as processors--each entity carries out its own computations, and passes on state information to its immediate neighbors, who use it as input for their own computations. Each entity may be running its own program, and what we would be interested in is the global behavior of the system over time.

With this perspective in mind, a "cellular automaton" is an array (in two or more dimensions) of identical entities called "cells," which interact with one another. Cells are distinguished by the following three important properties:

• State--the current state of a cell is a variable (or more generally, an n-tuple) that describes it.
• Neighborhood--the neighborhood of a cell is a specification of the...