A Brief Introduction To Cellular Automata

by Moshe Sipper

Cellular automata (CA) were originally conceived by Ulam and von Neumann in the 1940s to provide a formal framework for investigating the behavior of complex, extended systems [vN66, Sip02]). CAs are dynamical systems in which space and time are discrete. A cellular automaton consists of a regular grid of cells, each of which can be in one of a finite number of k possible states, updated synchronously in discrete time steps according to a local, identical interaction rule. The state of a cell is determined by the previous states of a surrounding neighborhood of cells [Wol84b, TM87].

The infinite or finite cellular array (grid) is n-dimensional, where n=1,2,3 is used in practice. The identical rule contained in each cell is essentially a finite state machine, usually specified in the form of a rule table (also known as the transition function), with an entry for every possible neighborhood configuration of states. The neighborhood of a cell consists of the surrounding (adjacent) cells. For one-dimensional CAs, a cell is connected to r local neighbors (cells) on either side, where r is a parameter referred to as the radius (thus, each cell has 2r+1 neighbors, including itself). For two-dimensional CAs, two types of cellular neighborhoods are usually considered: 5 cells, consisting of the cell along with its four immediate nondiagonal neighbors, and 9 cells, consisting of the cell along with its eight surrounding neighbors. The term configuration refers to an assignment of states to cells in the grid. When considering a finite-sized grid, spatially periodic boundary conditions are frequently applied, resulting in a circular grid for the one-dimensional case, and a toroidal one for the two-dimensional case. A one-dimensional CA is illustrated in Figure 1 (based on [Mit96]).

Figure 1: Illustration of a one-dimensional, 2-state CA (based on [Mit96]). Each cell can be in one of two states, denoted 0 and 1. The connectivity radius is r=1, meaning that each cell has two neighbors, one to its immediate left and one to its immediate right. Grid size is N=15. The rule table for updating the grid is shown on top. The grid configuration over one time step is shown at the bottom. Spatially periodic boundary conditions are applied, meaning that the grid is viewed as a circle, with the leftmost and rightmost cells each acting as the other's neighbor.

Over the years CAs have been applied to the study of general phenomenological aspects of the world, including communication, computation, construction, growth, reproduction, competition and evolution (see, e.g., [Sip02, TM87, Bur70, Smi69, PSZ96]). One of the most well-known CA rules, namely the ``game of life'', was conceived by Conway in the late 1960s  [Gar70, Gar71] and was shown by him to be computation-universal [BCG82]. A review of computation theoretic results is provided in [CHY90].

The question of whether cellular automata can model not only general phenomenological aspects of our world, but also directly model the laws of physics themselves was raised in [Tof77, FT82]. A primary theme of this research is the formulation of computational models of physics that are information-preserving, and thus retain one of the most fundamental features of microscopic physics, namely reversibility [FT82, Mar84, Tof80]. CAs have been used to provide extremely simple models of common differential equations of physics, such as the heat and wave equations  [Tof84] and the Navier-Stokes equation [HDP76, FHP86]. CAs also provide a useful discrete model for a branch of dynamical systems theory which studies the emergence of well-characterized collective phenomena such as ordering, turbulence, chaos, symmetry-breaking, fractality, etc. [Vic84, BG85]. The systematic study of CAs in this context was pioneered by Wolfram and studied extensively by him, identifying four qualitative classes of CA behavior (referred to as Wolfram classes), with analogs in the field of dynamical systems [Wol84b, Wol83, Wol84a]. Finally, biological modeling has also been carried out using CAs (see, e.g., review by [EEK93]).

Go to Cellular Programming page.

M. Sipper, Machine Nature: The Coming Age of Bio-Inspired Computing, McGraw-Hill, New York, 2002.