cellular automata

In the 1970s, British mathematician John H. Conway invented a pastime called the Game of Life, which was pop-ularized in Martin Gardner’s column in Scientific American. In this game (better termed a simulation), each cell in a grid “lived” or “died” according to the following rules:

1.  A living cell remains alive if it has either two or three living neighbors.

2.  A dead cell becomes alive if it has three living neighbors.

3.  A living cell dies if it has other than two or three living neighbors.

Investigators created hundreds of starting patterns of liv-ing cells and simulated how they changed as the rules were repeatedly applied. (Each application of the rules to the cells in the grid is called a generation.) They found, for example, that a simple pattern of three living cells in a row “blinked” or switched back and forth between a horizon-tal and vertical orientation. Other patterns, called “glider guns” ejected smaller patterns (gliders or spaceships) that traveled across the grid.

The Game of Life is an instance of the general class called cellular automata. Each cell operates like a tiny com-puter that takes as input the states of its neighbors and produces its own state as the output. (See also finite state machine.) The cells can be arranged in one (linear), two (grid), or three dimensions, and a great variety of sets of rules can be applied to them, ranging from simple variants of Life to exotic rules that can take into account how long a cell has been alive, or subject it to various “environmental” influences.

Applications

Cellular automata theory has been applied to a variety of fields that deal with the complex interrelationships of com-ponents, including biology (microbe growth and popula-tion dynamics in general), ecology (including forestry), and animal behavior, such as the flight of birds. (The cues that a bird identifies in its neighbors are like the input conditions for a cell in a cellular automaton. The “output” would be the bird’s flight behavior.)

The ability of cellular automatons to generate a rich complexity from simple components and rules mimics the development of life from simple components, and thus cel-lular automation is an important tool in the creation and study of artificial life. This can be furthered by com-bining a set of cellular automation rules with a genetic algorithm, including a mechanism for inheritance of characteristics. Cellular automation principles can also be applied to engineering in areas such as pattern or image recognition.

In 2002, computer scientist and mathematician Stephen Wolfram (developer of the Mathematica program) published a book titled A New Kind of Science that undertakes the modest project of explaining the fundamental structure and behavior of the universe using the principles of cellular automation. Time will tell whether this turns out to be simply an idiosyncratic (albeit interesting) approach or a generally useful paradigm.