4. Parallel Computing 14. Introduction

Figure 301: Four- vs. eight-neighbor cellular automata

Cellular automata were studied early by John von Neumann. He showed how Turing

machines can be embedded within them, and moreover how they can be made to

reproduce themselves. A popular cellular automaton is Conway's "Game of Life". Life is

a two-dimensional cellular automaton in which each cell has eight neighbors and only

two states (say "living" and "non-living", or simply 1 and 0). The non-living state

corresponds to the quiescent state described earlier.

The transition rules for Life are very simple:  If three of a cell's neighbors are living, the

cell itself becomes living. Also, if a cell is living, then if its number of living neighbors is

other than two or three, it becomes non-living.

The following diagram suggests the two kinds of cases in which the cell in the center is

living in the next state. Each of these rules is only an example. A complete set of rules

would number sixteen.