The first researcher of Cellular Automata was
John Von Neumann
, he developed a 29 state model of a two dimensional grid of cells that was able to both self-replicate itself and compute the solution to any problem using a
Von Neumann worked on his CA right up until his death in 1953, after which
completed his mathematical proof of universality. This model was extremely complex and large requiring an excess of over 150,000 cells;
E. F. Codd
distilled it into an
model preserving all its properties in 1968.
At Cambridge starting in 1970
John H. Conway
developed the simplest model of the cellular automaton called
"The Game of Life"
. In this CA model there is a two dimensional grid of cells that have only two states (alive or dead), their next state is determined by their 8 immediate neighbors and the center cell
- this is in contrast to the 5 cell neighborhood of Von Neumann's model.
Although there is no self-replication mechanism in the
game of life it is able to compute because of the presence of a multitude of
that can move information and interact. Through the strategic placement of
, first discovered by
William R. Gosper
, we can develop nand and nor logic gates from which any digital circuit can be simulated and hence any computational problem.
A further simplification of Von Neumann and Codd's CA was accomplished by
Christopher G. Langton
(but without the ability of universal computation).
Random Boolean Networks
are also an interesting stable substrate in which one can investigate
the cyclic behavior of interconnected cells and their applications.