A cellular automaton is a collection of "colored" cells on a grid of specified shape that evolves through a number of discrete
time steps according to a set of rules based on the states of neighboring cells.
The rules are then applied iteratively for as many time steps as desired. von Neumann
was one of the first people to consider such a model, and incorporated a cellular
model into his "universal constructor." Cellular automata were studied
in the early 1950s as a possible model for biological systems (Wolfram 2002, p. 48).
Comprehensive studies of cellular automata have been performed by S. Wolfram
starting in the 1980s, and Wolfram's fundamental research in the field culminated
in the publication of his book A New Kind of Science (Wolfram 2002) in which
Wolfram presents a gigantic collection of results concerning automata, among which
are a number of groundbreaking new discoveries.
The Season 2 episode "Bettor or Worse" (2006) of the television crime drama
NUMB3RS mentions onedimensional cellular automata.
Cellular automata come in a variety of shapes and varieties. One of the most fundamental properties of a cellular automaton is the type of grid
on which it is computed. The simplest such "grid" is a onedimensional
line. In two dimensions, square,
triangular, and hexagonal grids may be considered. Cellular automata may also
be constructed on Cartesian grids in arbitrary numbers of dimensions, with the dimensional integer lattice being the most
common choice. Cellular automata on a dimensional integer
lattice are implemented in Mathematica as CellularAutomaton[rule, init, steps].
The number of colors (or distinct states) a cellular automaton
may assume must also be specified. This number is typically an integer, with (binary) being the simplest choice. For a binary
automaton, color 0 is commonly called "white," and color 1 is commonly
called "black". However, cellular automata having a continuous range of
possible values may also be considered.
In addition to the grid on which a cellular automaton lives and the colors its cells may assume, the neighborhood over
which cells affect one another must also be specified. The simplest choice is "nearest
neighbors," in which only cells directly adjacent to a given cell may be affected
at each time step. Two common neighborhoods in the case of a twodimensional cellular
automaton on a square grid are the
socalled Moore neighborhood
(a square neighborhood) and the von
Neumann neighborhood (a diamondshaped neighborhood).
The simplest type of cellular automaton is a binary, nearestneighbor, onedimensional automaton. Such automata were called "elementary cellular automata" by S. Wolfram, who
has extensively studied their amazing properties (Wolfram 1983; 2002, p. 57).
There are 256 such automata, each of which can be indexed by a unique binary number
whose decimal representation is known as the "rule" for the particular
automaton. An illustration of rule 30
is shown above together with the evolution it produces after 15 steps starting from
a single black cell.
A slightly more complicated class of cellular automata are the nearestneighbor, color, onedimensional totalistic cellular automata. In such automata, it is the average
of adjacent cells that determine the evolution, and the simplest nontrivial examples
have colors. For these automata, the set
of rules describing the behavior can be encoded as a digit ary number known as a "code." The rules
and 300 steps of the ternary () code 912 automaton are illustrated above.
In two dimensions, the bestknown cellular automaton is Conway's game of life, discovered by J. H. Conway in 1970 and popularized
in Martin Gardner's Scientific American columns. Life
is a binary () totalistic cellular automaton with a Moore neighborhood of range . 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. An animation of the life construction known as a puffer train is illustrated above.
WireWorld is another common twodimensional
cellular automaton.
The theory of cellular automata is immensely rich, with simple rules and structures being capable of producing a great variety of unexpected behaviors. For example,
there exist universal
cellular automata that are capable of simulating the behavior of any other cellular
automaton or Turing machine.
It has even been proved by Gacs (2001) that there exist faulttolerant universal
cellular automata, whose ability to simulate other cellular automata is not hindered
by random perturbations provided that such perturbations are sufficiently sparse.
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: SpringerVerlag, 1989.
Burks, A. W. (Ed.). Essays on Cellular Automata. UrbanaChampaign, 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, 19951996, Vol. 3.
Providence, RI: Amer. Math. Soc., pp. 7081, 1996.
Dewdney, A. K. The Armchair Universe: An Exploration of Computer Worlds.
New York: W. H. Freeman, 1988.
Gacs, P. "Reliable Cellular Automata with SelfOrganization." J. Stat.
Phys. 103, 45267, 2001.
Gardner, M. "The Game of Life, Parts IIII." Chs. 2022 in Wheels, Life, and other Mathematical Amusements. New York:
W. H. Freeman, 1983.
Goles, E. and Martínez, S. (Eds.). Cellular Automata and Complex Systems. Amsterdam, Netherlands:
Kluwer, 1999.
Gutowitz, H. (Ed.). Cellular Automata: Theory and Experiment. Cambridge, MA:
MIT Press, 1991.
Hopcroft, J. E. and Ullman, J. D. Introduction to Automata Theory, Languages, and Computation.
Reading, MA: Addison Wesley, 1979.
Hopcroft J. E. "An Algorithm
for Minimizing the States in a Finite Automaton." In The Theory of Machines and Computations (Ed. Z. Kohavi.)
New York: Academic Press, pp. 189196, 1971.
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, 219258, 1984.
McIntosh, H. V. "Cellular Automata Miscellanea." http://delta.cs.cinvestav.mx/~mcintosh/.
Preston, K. Jr. and Duff, M. J. B. Modern Cellular Automata: Theory and Applications. New
York: Plenum, 1985.
RangelMondragon, J. "A Catalog of Cellular Automata."
http://library.wolfram.com/infocenter/MathSource/505/.
Sigmund, K. Games of Life: Explorations in Ecology, Evolution and Behaviour.
New York: Penguin, 1995.
Sloane, N. J. A. Sequence A006977/M2497
in "The OnLine Encyclopedia of Integer Sequences."
Sloane, N. J. A. and Plouffe, S. Figure M2497 in 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.
Weisstein, E. W. "Books about Cellular Automata." http://www.ericweisstein.com/encyclopedias/books/CellularAutomata.html.
Wolfram, S. "Statistical Mechanics of Cellular Automata." Rev. Mod.
Phys. 55, 601644, 1983.
Wolfram, S. "Twenty Problems in the Theory of Cellular Automata." Physica
Scripta T9, 170183, 1985.
Wolfram, S. (Ed.). Theory and Application of Cellular Automata. Reading, MA:
AddisonWesley, 1986.
Wolfram, S. Cellular Automata and Complexity: Collected Papers. Reading,
MA: AddisonWesley, 1994.
Wolfram, S. A New Kind of Science. Champaign, IL: Wolfram Media, 2002.
Wuensche, A. and Lesser, M. The Global Dynamics of Cellular Automata: An Atlas of Basin of
Attraction Fields of OneDimensional Cellular Automata. Reading, MA: AddisonWesley,
1992.
