3. Qualitative Characterization of Cellular Automaton Behaviour

This section discusses some qualitative features of cellular automaton evolution, and gives empirical evidence for the existence of four basic classes of behaviour in cellular automata. Section 4 introduces some methods for quantitative analysis of cellular automata. Later sections use these methods to suggest fundamental characterizations of the four cellular automaton classes.

Figure 1 shows the pattern of configurations generated by evolution according to each of the 32 possible legal totalistic rules with and , starting from a ``disordered'' initial configuration (in which each site value is independently chosen as 0 or 1 with probability ). Even with such a structureless initial state, many of the rules are seen to generate patterns with evident structure. While the patterns obtained with different rules all differ in detail, they appear to fall into four qualitative classes:

1. Evolution leads to a homogeneous state (realized for codes 0, 4, 16, 32, 36, 48, 54, 60 and 62).
2. Evolution leads to a set of separated simple stable or periodic structures (codes 8, 24, 40, 56 and 58).
3. Evolution leads to a chaotic pattern (codes 2, 6, 10, 12, 14, 18, 22, 26, 28, 30, 34, 38, 42, 44, 46 and 50).
4. Evolution leads to complex localized structures, sometimes long-lived (codes 20 and 52).

Some patterns (e.g. code 12) assigned to class 3 contain many triangular ``clearings'' and appear more regular than others (e.g. code 10). The degree of regularity is related to the degree of irreversibility of the rules, as discussed in section 7.

Figure 2 shows patterns generated from several different initial states according to a few of the cellular automaton rules of fig. 1. Patterns obtained with different initial states are seen to differ in their details, but to exhibit the same characteristic qualitative features. (Exceptional initial states giving rise to different behaviour may exist with low or zero probability.) Figure 3 shows the differences between patterns generated by various cellular automaton rules from initial states differing in the value of a single site.

[ Figure 1 ] Evolution of all possible legal one-dimensional totalistic cellular automata with and . gives the number of possible values for each site, and gives the range of the cellular automaton rules. A range allows the nearest and next-nearest neighbours of a site to affect its value on the next time step. Time evolution for totalistic cellular automata is defined by eqs. (2.2) and (2.7). The initial state is taken disordered, each site having values 0 and 1 with independent equal probabilities. Configurations obtained at successive time steps in the cellular automaton evolution are shown on successive horizontal lines. Black squares represent sites with value 1; white squares sites with value 0. All the cellular automaton rules illustrated are seen to exhibit one of four qualitative classes of behaviour.

Figures 4, 5 and 6 show examples of various sets of totalistic cellular automata. Figure 4 shows some , rules, fig. 5 some , rules, and fig. 6 some , rules. The patterns generated are all seen to be qualitatively similar to those of fig. 1, and to lie in the same four classes.

Patterns generated by all possible , cellular automata were given in ref. 1, and are found to lie in classes 1, 2 and 3. Totalistic , rules are found to give patterns typical of all , rules. In general, totalistic rules appear to exhibit no special simplifications, and give rise to behaviour typical of all cellular automaton rules with given and .

An extensive sampling of many other cellular automaton rules supports the general conjecture that the four classes introduced above cover all one-dimensional cellular automata. (1)

[ Figure 2 ] Evolution of some cellular automata illustrated in fig. 1 from several disordered states. The first two initial states shown differ by a change in the values of two sites, the next by a change in the values of ten sites. The last state is completely different.

Table 1 gives the fractions of various sets of cellular automata in each of the four classes. With increasing and , class 3 becomes overwhelmingly the most common. Classes 1 and 2 are decreasingly common. Class 4 is comparatively rare, but becomes more common for larger and .

[ Table 1 ] Approximate fractions of legal totalistic cellular automaton rules in each of the four basic classes.

``Reducible'' cellular automata (mentioned in section 2) may generate patterns which contain features from several classes. In a typical case, fixed or propagating ``membranes'' consisting of sites with a particular value may separate regions containing patterns from classes 3 or 4 formed from sites with other values.

This paper concerns one-dimensional cellular automata. Two-dimensional cellular automata also appear to exhibit a few distinct classes of behaviour. Superficial investigations [5] suggest that these classes may in fact be identical to the four found in one-dimensional cellular automata.

[ Figure 3 ] Differences modulo two between patterns generated by the time evolution of several cellular automata illustrated in fig. 1 with disordered states differing by a change in the value of a single site.

[ Figure 4 ] Examples of the evolution of typical cellular automata with (three possible site values) and (only nearest neighbours included in time evolution rules). White squares represent value 0, grey squares value 1, and black squares value 2. The initial state is taken disordered, with each site having values 0, 1 and 2 with equal independent probabilities.

[ Figure 5 ] Examples of the evolution of typical , cellular automata from a disordered initial state.

[ Figure 6 ] Examples of the evolution of typical , cellular automata from a disordered initial state. Darker squares represent sites with larger values.

previous  l  next