2. Cellular Automata

A 1-dimensional cellular automaton [12, 13] consists of a line of sites with values between and . These values are updated in parallel (synchronously) in discrete time steps according to a fixed rule of the form

Much of this paper is concerned with the study of a particular , cellular automaton, described in Section 3.

For mathematical purposes, it is often convenient to consider cellular automata with an infinite number of sites. But practical implementations must contain a finite number of sites . These are typically arranged in a circular register, so as to have periodic boundary conditions, given in the case by

It is also possible to arrange the sites in a feedback shift register (cf. [4]), with boundary conditions

Cellular automata can be considered as discrete approximations to partial differential equations, and used as direct models for a wide variety of natural systems (e.g., [14]). They can also be considered as discrete dynamical systems corresponding to continuous mappings on the Cantor set (e.g., [15]). Finally they can be viewed as computational systems, whose evolution processes information contained in their initial configurations (e.g., [16]).

Despite the simplicity of their construction, cellular automata are found to be capable of diverse and complex behaviour. Figure 2.1 shows some patterns generated by evolution according to various cellular automaton rules, starting from typical disordered initial conditions. Four basic outcomes are seen [15]: (1) the pattern becomes homogeneous (fixed point), (2) the pattern degenerates into simple periodic structures (limit cycles), (3) the pattern is aperiodic, and appears chaotic, and (4) complicated localized structures are produced. The first two classes of cellular automata yield readily predictable behaviour, and show no seemingly random elements. But the third class gives rise to behaviour that is more complex. They can produce patterns whose features cannot readily be predicted in detail, and in fact often seem completely random. Such cellular automata can be used as models of randomness in nature. They can also be considered as abstract mathematical systems, and used for practical random sequence generation.

Figure 2.1 shows patterns produced by evolution according to various cellular automaton rules, starting from typical disordered initial conditions, in which the value of each site is randomly chosen to be zero or one. Figure 2.2 shows some patterns obtained instead by evolution from a very simple initial condition containing a single nonzero site. With such simple initial conditions, some class 3 cellular automata yield rather simple patterns, which are typically periodic or at least self similar (almost periodic). There are nevertheless class 3 cellular automata which yield complex patterns, even from simple initial states. Their evolution can intrinsically produce apparent randomness, without external input of random initial conditions. It is such ''autoplectic'' systems [11] which seem most promising for explaining randomness in nature, or for use as practical random sequence generation procedures.

Many class 3 cellular automata seem to perform very complicated transformations on their initial conditions. Their evolution thus corresponds to a complicated computation. But any predictions of the cellular automaton behaviour must also be obtained through computations. Effective predictions require computations that are more sophisticated than those corresponding to the cellular automaton evolution itself. One suspects however that the evolution of many class 3 cellular automata is in fact computationally as sophisticated as that of any (physically realizable) system can be [18, 19]. It is thus ''computationally irreducible,'' and its outcome can effectively be found only by direct simulation or observation. There are no general computational shortcuts or finite mathematical formulae for it. As a consequence, many questions concerning infinite time or infinite size limits cannot be answered by bounded computations, and must be considered formally undecidable. In addition, questions about finite time or finite size behaviour, while ultimately computable, may be computationally intractable, and could require, for example, exponential time computations.

[ Figure 2.1 ] Patterns generated by evolution of various , cellular automata from disordered initial states. Successive lines give configurations obtained on successive time steps, with white and black squares representing sites with values 0 and 1 respectively. The coefficient of in the binary decomposition of each rule number gives the value of the function in Eq. (2.1) for the neighbourhood whose site values form the integer (cf. [17]).

Most class 3 cellular automata are expected to be computationally irreducible. A few rules however have special simplifying features which make predictions and analysis possible. One class of such rules are those for which the function is linear (modulo ) in the . Such cellular automata are analogous to linear feedback shift registers [4]. An example with is

where stands for exclusive disjunction (this is rule number 60 in the scheme of [17]). Linear cellular automata satisfy a superposition principle, which implies that patterns generated with arbitrary initial states can be obtained as appropriate superpositions of the self-similar pattern produced with a single nonzero initial site (as illustrated in Fig. 2.2). As a result, it is possible to give a complete algebraic description of the behaviour of the system [20], and to deduce the outcome of its evolution by a much reduced computation.

Most class 3 cellular automata are however nonlinear. No general methods to predict their behaviour have been found, and from their likely computational irreducibility one expects that no such methods even in principle exist. In studying such systems one must therefore to a large extent forsake conventional mathematical techniques and instead rely on empirical and experimental mathematical results.

[ Figure 2.2 ] Patterns generated by evolution of various , cellular automata from an initial state containing a single nonzero site. Complex patterns are seen to be produced even with such simple initial conditions.

previous  l  next