What is a cellular automaton (CA)? Begin with a lattice of sites (this can be finite or infinite). Let each site be in one of a finite number of states. This is the initial configuration of the system. Define a neighborhood that consists of a finite number of other sites. At each time step, each site checks the states of its neighbors. It then makes a computation, which is based on the status of its neighbors, to decide what state it will be in next time. All of the lattice sites do the same thing, and after making their computations, they update (meaning change states or not) simultaneously. A CA rule is said to be local because each site in the system is only affected by the sites in its finite neighborhood. It is homogeneous, or translation invariant, because the neighborhood for each site in the system is defined in the same way, and each site updates according to the same rule. It is deterministic because its rule is so. It is discrete, in time, because the sites update at discrete times. I t is discrete, in space, because its universe is a lattice. It is dynamic because the sites update at each time step and it is parallel because the sites update synchronously.

The most famous example of a CA is John Horton Conway's celebrated Game of Life. The universe is an infinite two-dimensional grid. There are two states, 0 and 1, which we think of as dead and live, respectively. The neighborhood of a site consists of the eight sites surrounding it. Each time step a dead site will become live if there are exactly three live sites in its neighborhood. A site that is live will stay live if two or three of its neighbors are also live. At time zero the player gets to decide which sites are live and which are dead. After that, the rules of the game take over: every time step all of the sites update according to the deterministic rule we have just described.

Cellular automaton rules are intrinsically interesting and they are also becoming a popular tool for modeling problems in fields such as chemistry, mathematical biology, and population ecology. As one example, they are being used to study the extent to which spatial variation in ecological systems influences the ability of a species to survive. The Larger than Life family of CA rules (the topic of my dissertation) contains some nonlinear population dynamics which are prototypes for such spatial models.

 

Cellular Automaton Links

Callahan's Life page

Links to the latest remarkable discoveries about Conway's Game of Life.

 

Primordial Soup Kitchen

David Griffeath's gallery of cellular automaton images and their recipes. If you go ... be sure to check out Caffeine (java) and the Kitchen Sink.

 

Cellular Automaton FAQ

Contributions from the cellular automaton community, edited by Howard Gutowitz.

 

"Which 'Life'-Like Systems Have Gliders?"

David Eppstein presents charts of the range one rules for which he has found gliders, as well as several search programs (written for range one, outer totalistic rules).

 

Evolving Cellular Automata

Scientists working on the Evolving Cellular Automata Project at the Santa Fe Institute are researching the use of genetic algorithms to discover cellular automaton rules.

 

Rudy Rucker's home page

Free "gnarly software" by Rudy Rucker & friends.

 

return to main page