Mathematical Approaches

Rather than describing specific applications of cellular automata, this article concentrates on general mathematical features of their behaviour. Two complementary approaches provide characterizations of the four classes of behaviour seen in Fig. 3.

In the first approach [2], cellular automata are viewed as discrete dynamical systems (see ref. [14]), or discrete idealizations of partial differential equations. The set of possible (infinite) configurations of a cellular automaton forms a Cantor set; cellular automaton evolution may be viewed as a continuous mapping on this Cantor set. Quantities such as entropies, dimensions and Lyapunov exponents may then be considered for cellular automata.

In the second approach [3], cellular automata are instead considered as information-processing systems (see ref. [15]), or parallel-processing computers of simple construction. Information represented by the initial configuration is processed by the evolution of the cellular automaton. The results of this information processing may then be characterized in terms of the types of formal languages generated. (Note that the mechanisms for information processing in natural system appear to be much closer to those in cellular automata than in conventional serial-processing computers: cellular automata may, therefore, provide efficient media for practical simulations of many natural systems.)

previous  l  next