Automata

ALife Home

Introduction

Automata

Genetic Algorithms

Neural Networks

Experiments

People

Timeline

References

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 universal Turing machine.

Von Neumann worked on his CA right up until his death in 1953, after which Arthur Burks 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 8-state [cod68] 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" Sun Java Applet . 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 "gliders" that can move information and interact. Through the strategic placement of "glider guns" , 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 using his self-reproducing loops (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.

michael@obrienm.com
Last Updated: Ottawa, Canada

Introduction Introduction Boolean Networks Boolean Networks Artificial Life Home Artificial Life Home