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 cellularmodel into his ``universal constructor.'' von Neumann proved that an automaton consisting ofcells with four orthogonal neighbors and 29 possible states would be capable of simulating a Turing Machine for someconfiguration 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 berepresented with an 8-bit binary number, as shown by Stephen Wolfram. Wolfram furtherrestricted 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 originallydone by hand, the computer revolution soon arrived and allowed more extensive patterns to be studied andpropagated.

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. SequenceA006977/M2497in ``An On-Line Version of the Encyclopedia of Integer Sequences.''http://www.research.att.com/~njas/sequences/eisonline.html and extended entry inSloane, 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.

• Fortunate Prime
• Forward Difference
• Fountain
• Four Coins Problem
• Four-Color Theorem
• Fourier-Bessel Series
• Fourier-Bessel Transform
• Fourier Cosine Series
• Fourier Cosine Transform
• Fourier Integral
• Fourier Matrix
• Fourier-Mellin Integral
• Fourier Series
• Fourier Series--Power Series
• Fourier Series--Right Triangle
• Fourier Series--Square Wave
• Fourier Series--Triangle
• Fourier Series--Triangle Wave
• Fourier Sine Series
• Fourier Sine Transform
• Fourier-Stieltjes Transform
• Fourier Transform
• Fourier Transform--1
• Fourier Transform--Cosine
• Fourier Transform--Delta Function