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 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.

**References**

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.

© 1996-9

1999-05-26