Cellular Automata

A one-dimensional cellular automaton consists of a line of sites, with each site carrying a value 0 or 1 (or in general 0, , ). The value of the site at each position is updated in discrete timesteps according to an identical deterministic rule depending on a neighbourhood of sites around it:

Even with and or 2, the overall behaviour of cellular automata constructed in this simple way can be extremely complex.

Consider first the patterns generated by cellular automata evolving from simple `seeds' consisting of a few non-zero sites. Some local rules give rise to simple behaviour; others produce complicated patterns. An extensive empirical study suggests that the patterns take on four qualitative forms, illustrated in Fig. 1:

[ Figure 1 ] Classes of patterns generated by the evolution of cellular automata from simple `seeds'. Successive rows correspond to successive time steps in the cellular automaton evolution. Each site is updated at each time step according to equation (1) by cellular automaton rules that depend on the values of a neighbourhood of sites at the previous time step. Sites with values 0 and 1 are represented by white and black squares, respectively. Despite the simplicity of their construction, patterns of some complexity are seen to be generated. The rules shown exemplify the four classes of behaviour found. (The first three are , rules with rule numbers [1] 128, 4 and 126, respectively; the fourth is a , rule with totalistic code [2] 52.) In the third case, a self-similar pattern is formed.

1. disappears with time;
2. evolves to a fixed finite size;
3. grows indefinitely at a fixed speed;
4. grows and contracts irregularly.

Patterns of type 3 are often found to be self-similar or scale invariant. Parts of such patterns, when magnified, are indistinguishable from the whole. The patterns are characterized by a fractal dimension [5]; the value is the most common. Many of the self-similar patterns seen in natural systems may in fact, be generated by cellular automaton evolution.

Figure 3 shows the evolution of cellular automata from initial states where each site is assigned each of its possible values with an independent equal probability. Self-organization is seen: ordered structure is generated from these disordered initial states, and in some cases considerable complexity is evident.

Different initial states with a particular cellular automaton rule yield patterns that differ in detail, but are similar in form and statistical properties. Different cellular automaton rules yield very different patterns. An empirical study, nevertheless, suggests that four qualitative classes may be identified, yielding four characteristic limiting forms:

1. spatially homogeneous state;
2. sequence of simple stable or periodic structures;
3. chaotic aperiodic behaviour;
4. complicated localized structures, some propagating.

All cellular automata within each class, regardless of the details of their construction and evolution rules, exhibit qualitatively similar behaviour. Such universality should make general results on these classes applicable to a wide variety of systems modelled by cellular automata.

previous  l  next