Problem 7

How is different behaviour distributed in the space of cellular automaton rules?

Random sampling yields some empirical indications of the frequencies of different classes of behaviour among cellular automaton rules of various kinds. For symmetric one-dimensional cellular automata, class 1 and 2 cellular automata appear to become progressively less common as and increase; class 3 becomes more common, and class 4 slowly becomes less common. In two-dimensional cellular automata, class 3 is overwhelmingly the most common; class 4 is very rare [12]. It seems that class 3 behaviour in any ``direction'' in the cellular automaton state space leads to overall class 3 behaviour. And as the number of degrees of freedom in the rules increases, the chance that this happens for one of the directions increases. For very large and a direct statistical treatment of the set of cellular automaton rules may well be possible.

There are many common features in the behaviour of cellular automata with apparently very different rules. It is not clear to what extent a direct equivalence exists between rules with qualitatively similar behaviour. In some cases, different rules may be related through invertible cellular automaton mappings. The nature of the equivalence classes of cellular automata generated in this way is presumably determined largely by the structure of the group of invertible cellular automaton mappings.

There are various ways to define distances in the space of cellular automaton rules. There are often cellular automata whose rules differ only slightly, but whose behaviour is very different. Nevertheless, it should be possible to find families of cellular automaton rules with closely related behaviour. For example, one may consider totalistic rules [5] in which the function that gives the new value of a site in terms of the sum of the old values in its neighbourhood is a discrete approximation to a function that involves a continuous parameter [23]. The behaviour of different cellular automaton rules obtained by changing this parameter may be compared with the behaviour found in iterated mappings of an interval of the real line (e.g., [24]) according to the same function. There are indications of a significant correspondence [23]. As the parameter is increased, regular periodic (class 2) cellular automaton behaviour can exhibit period doubling. Then as the parameter is further increased, chaotic (class 3) behaviour can occur. Class 4 seems to appear as an intermediate phenomenon.

previous  l  next