On cellular automata, self-reproduction, the Garden of Eden, and the game "life"

by Martin Gardner

Scientific American

John Horton Conway's game "life," last October's topic, stirred such interest among computer scientists that this month's department will again be devoted to the game. Before reporting as many new discoveries as possible I should like to discuss some highlights in the history of "cellular automata theory," the field in which games similar to Conway's are being investigated.

It all began about 1950, when John von Neumann set himself the task of proving the possibility of self-duplicating automata. Such a machine, given proper instructions, would build an exact duplicate of itself. Each of the two machines would then build another, the four would become eight, and so on. (This proliferation of self-replicating automata is the basis of Lord Dunsany's amusing 1951 novel The Last Revolution.) Von Neumann first proved his case with "kinematic" models of a machine that could roam through a warehouse of parts, select needed components, and put together a copy of itself. Later, adopting an inspired suggestion by his friend Stanislaw M. Ulam, he showd the possibility of such machines in a more elegant and abstract way.

Von Neumann's new proof used what is now called a "uniform cellular space" equivalent to an infinite checkerboard. Each cell can have any finite number of "states," including a "quiescent" (or empty) state, and a finite set of "neighbor" cells that can influence its state. The pattern of state changes in discrete time steps according to a set of "transition rules" that apply simultaneously to every cell. The cells symbolize the basic parts of a finite-state automaton and a configuration of live cells is an idealized model of such a machine. Conway's game is based on just such a space. His neighborhood consists of the eight cells surrounding a cell; each cell has two states (empty or filled), and his transition rules are the birth, death, and survival rules I explained in October. Von Neumann, applying transition rules to a space in which each cell has 29 states and four orthoganally adjacent neighbors, proved the existance of a configuration of about 200,000 cells that would self-reproduce.

The reason for such an enormous configuration is that, for von Neumann's proof to apply to actual automata, it was necessary that his cellular space be capable of simulating a Turing machine: an idealized automaton, named for its inventor, the British mathematician A. M. Turing, capable of performing any desired calculation. By embedding this universal computer in his configuration, von Neumann was able to produce a universal constructor. Because it could in principle construct any desired configuration by stretching "arms" into an empty region of cellular space, it would self-replicate when given a blueprint of itself. Since von Neumann's death in 1957 his existance proof (the actual construction is too vast to construct and manipulate) has been greatly simplified. The latest and best reduction, by Edwin Roger Banks, a mechanical engineering graduate student at the Massachusetts Institute of Technology, does the job with cells of only four states.

Self-replication in a trivial sense--without using configurations
that contain Turing machines--is easy to achieve.
A delightfully simple example,
discovered by Edward Fredkin of M.I.T. about 10 years ago,
uses two-state cells,
the von Neumann neighborhood of four orthoganally adjacent cells
and the following parity rule:
Each cell with an even number of neighbors (0, 2, 4) at time *t*
becomes or remains empty at time *t* + 1,
and each cell with an odd number of neighbors (1, 3) at time *t*
becomes or remains live at time *t* + 1.
It is not hard to show that after 2^{n} moves
(*n* varying with different patters)
any initial pattern of live cells will reproduce itself four times--above,
below, left and right of an empty space that it formerly occupied.
The four replicas will be displaced
2^{n}
cells from the vanished original.
The new pattern will, of course, replicate again after andother
2^{n}
steps,
so that the duplicates keep quadrupling
in the endless series 1, 4, 16, 64, ....
The illustration below shows two quadruplings of a right tetromino.
Terry Winograd,
in a 1967 term paper written when he was an M.I.T. student,
generalized Fredkin's rule to other neighborhoods,
and number of dimensions,
and cells with any prime number of states.

Ulam investigated a variety of cellular automata games, experimenting with different neighborhoods, numbers of states and transition rules. In a 1967 paper "On Recursively Definied Geometrical Objects and Patterns of Growth," written with Robert G. Schrandt, Ulam described a number of different games. The upper illustration on this page