1. Introduction

Differential equations form the mathematical basis for most current models of natural systems. Cellular automata may be considered as an alternative and in some respects complementary basis for mathematical models of nature. Whereas ordinary differential equations are suitable for systems with a small number of continuous degrees of freedom, evolving in a continuous manner, cellular automata describe the behaviour of systems with large numbers of discrete degrees of freedom.

In the simplest case, a cellular automaton consists of a line of sites, with each site having a value 0 or 1. The sequence of site values is the "configuration" of the cellular automaton. The cellular automaton evolves in discrete time steps. At each time step, the value of each site is updated according to a definite rule. The rule specifies the new value of a particular site in terms of its own old value, and the old values of sites in some neighbourhood around it. The neighbourhood is typically taken to include sites up to some small finite range from a particular site. Taking to be the value of a site at position and time step , one simple example of a cellular automaton rule is

With this rule, the value of a particular site is given by the sum modulo two of the values of its two nearest neighbours on the previous time step. Notice that the rule is applied in parallel (synchronously) to each site at each time step.

In general, the sites in a cellular automaton may take on any finite set of possible values, rather than simply 0 and 1. In addition, the sites may be arranged on a two or higher dimensional lattice (typically square, hexagonal or cubical), rather than on a line. As a further generalization, one may allow the value of a particular site to depend not only on values at the previous time step, but also on values from preceding time steps.

Cellular automata have five fundamental defining characteristics:

1. They consist of a discrete lattice of sites.
2. They evolve in discrete time steps.
3. Each site takes on a finite set of possible values.
4. The value of each site evolves according to the same deterministic rules.
5. The rules for the evolution of a site depend only on a local neighbourhood of sites around it.

With these characteristics, cellular automata provide rather general discrete models for homogeneous systems with local interactions. They may be considered as idealizations of partial differential equations, in which time and space are assumed discrete, and dependent variables taken on a finite set of possible values.

The discrete nature of cellular automata allows a direct and powerful analogy between cellular automata and digital computers to be drawn. The initial configuration for a cellular automaton corresponds to the "program" and "initial data" for a computation. "Processing" occurs through the time evolution of a cellular automaton, and the "results" of the computation are given by the configurations obtained. Whereas typical digital electronic computers process data serially, a few bits at a time, cellular automata process a large (or infinite) number of bits in parallel. Such parallel processing, expected to be crucial in the architecture of new generations of computers, is found in many natural systems.

next