Cellular Automaton

A grid (possibly 1-D) of cells which evolves according to a set of rules based on the states of surrounding cells. von Neumann was one of the first people to consider such a model, and incorporated a cellular model into his ``universal constructor.'' von Neumann proved that an automaton consisting of cells with four orthogonal neighbors and 29 possible states would be capable of simulating a Turing Machine for some configuration of about 200,000 cells (Gardner 1983, p. 227).

1-D automata are called ``elementary'' and are represented by a row of pixels with states either 0 or 1. These can be represented with an 8-bit binary number, as shown by Stephen Wolfram. Wolfram further restricted the number from $2^8=256$ to 32 by requiring certain symmetry conditions.

The most well-known cellular automaton is Conway's game of Life, popularized in Martin Gardner's Scientific American columns. Although the computation of successive Life generations was originally done by hand, the computer revolution soon arrived and allowed more extensive patterns to be studied and propagated.

See Life, Langton's Ant

References

Cellular Automata

Adami, C. Artificial Life. Cambridge, MA: MIT Press, 1998.

Buchi, J. R. and Siefkes, D. (Eds.). Finite Automata, Their Algebras and Grammars: Towards a Theory of Formal Expressions. New York: Springer-Verlag, 1989.

Burks, A. W. (Ed.). Essays on Cellular Automata. Urbana-Champaign, IL: University of Illinois Press, 1970.

Cipra, B. ``Cellular Automata Offer New Outlook on Life, the Universe, and Everything.'' In What's Happening in the Mathematical Sciences, 1995-1996, Vol. 3. Providence, RI: Amer. Math. Soc., pp. 70-81, 1996.

Dewdney, A. K. The Armchair Universe: An Exploration of Computer Worlds. New York: W. H. Freeman, 1988.

Gardner, M. ``The Game of Life, Parts I-III.'' Chs. 20-22 in Wheels, Life, and Other Mathematical Amusements. New York: W. H. Freeman, pp. 219 and 222, 1983.

Gutowitz, H. (Ed.). Cellular Automata: Theory and Experiment. Cambridge, MA: MIT Press, 1991.

Levy, S. Artificial Life: A Report from the Frontier Where Computers Meet Biology. New York: Vintage, 1993.

Martin, O.; Odlyzko, A.; and Wolfram, S. ``Algebraic Aspects of Cellular Automata.'' Communications in Mathematical Physics 93, 219-258, 1984.

Preston, K. Jr. and Duff, M. J. B. Modern Cellular Automata: Theory and Applications. New York: Plenum, 1985.

Sigmund, K. Games of Life: Explorations in Ecology, Evolution and Behaviour. New York: Penguin, 1995.

Sloane, N. J. A. Sequence A006977/M2497 in ``An On-Line Version of the Encyclopedia of Integer Sequences.'' http://www.research.att.com/~njas/sequences/eisonline.html and extended entry in Sloane, N. J. A. and Plouffe, S. The Encyclopedia of Integer Sequences. San Diego: Academic Press, 1995.

Toffoli, T. and Margolus, N. Cellular Automata Machines: A New Environment for Modeling. Cambridge, MA: MIT Press, 1987.

Wolfram, S. ``Statistical Mechanics of Cellular Automata.'' Rev. Mod. Phys. 55, 601-644, 1983.

Wolfram, S. (Ed.). Theory and Application of Cellular Automata. Reading, MA: Addison-Wesley, 1986.

Wolfram, S. Cellular Automata and Complexity: Collected Papers. Reading, MA: Addison-Wesley, 1994.

Wuensche, A. and Lesser, M. The Global Dynamics of Cellular Automata: An Atlas of Basin of Attraction Fields of One-Dimensional Cellular Automata. Reading, MA: Addison-Wesley, 1992.