The Game of Life was the brainchild of British mathematician John Conway. In a Scientific American article in October, 1970, Martin Gardner outlined the rules of life (as it has come to be known) as it was to be played on checkerboard with flat "counters" of two colors. The counters are used to indicate living cells, one color for newly born cells, and the other color for existing living cells.
In the Java applet below, Gardner's checkerboard has been replicated by a grid,
with each cell of the grid corresponding to a cell in Conway's "neighborhood".
You can run the game of life by:
Soon after its invention in 1970, John Conway's Game of Life
became a hit amongst mathematical gamers. In the original Scientific
American article, Conway conjectured that no pattern in life
could grow without bound, and even offered a prize of $50 to the first person
to come up with one. This was done in November, 1970, by the discovery of the
glider gun, which one of the options under initial
configurations in the game above. Many other fascinating patterns have
been discovered, a subset of which are available in the game above.
Conway's conjecture that no pattern in life could grow without
bound and the quick counter example to this conjecture, indicates the subtle
power behind the Game of Life. Life is a
cellular automaton, which is a uniform array of many identical cells
where each cell has a finite number of states (alive or dead for life
) and interacts with only a few neighbor cells. Cellular automaton
were originally investigated by John von Neumann in the early 1950's in his
book entitled The Theory of Self-Reproducing Automata. The
cellular automata created by von Neumann was in fact capable of simulating a
Turing machine. Consisting of cells with 29 states and four
orthogonally adjacent neighbors, the automata would self-reproduce with a
certain initial configuration that contained 200,000 cells! Since von
Neumann, his existence proof has been greatly simplified and now can be done
with cells of only 4 states. The Game of Life, in fact, has been
shown to be a universal computer, as powerful as a Turing machine!
The applications of cellular automata is broad. Cellular automata have been
used, as indicated by the name cellular, to model the biological
developmental of cells in living creatures. The cellular automata, along with a
class of formal languages called EOL languages, are a
fascinating intersection between biology and computation theory. In addition
to biology, "arrays of locally interacting cells are seen as potentially
useful models of physical systems, ranging from snowflakes to ferromagnets to
galaxies" [Omni, March 1984]. The interest in cellular
automata is due to the fact that they are discrete systems, each generation
of cells is a finite configuration of cells on an n-dimensional
grid. The discrete nature of cellular automata is in contrast to other
models of physical systems which are continuous, such as Maxwell's equations.
A discrete model of a physical systems makes an exact description
possible, as well as an exact description of the evolution of the system.
Stephen Wolfram, the inventor of Mathematica and founder of
Wolfram Research, has investigated four classes of cellular automata:
The simulation will then progress according to the 3 "genetic laws" developed
by Conway. These "genetic laws" are:
A "neighbor" cell in the game of life is a cell that is
reachable by a king on a chessboard. The survival, death, and birth of all
cells occurs simultaneously, and all cells together constitute a generation.
Life and the Theory of Computation
Wolfram has also published a
list of questions in his
1984 paper Twenty Problems in the Theory of Cellular Automata.
I invite you to take the challenge of solving the problems posed by Wolfram, or check out the other cellular automata online resources below, or just sit back and play the game.