More General Cellular Automata

The discussion so far has concentrated on the particular cellular automaton rule given by Eq. 1. This rule may be generalized in several ways. One family of rules is obtained by allowing the value of a site to be an arbitrary function of the values of the site itself and of its two nearest neighbors on the previous time step:

A convenient notation illustrated in Fig. 7 assigns a ``rule number'' to each of the 256 rules of this type. The rule number of Eq. 1 is 90 in this notation.

[ Figure 7 ] Assignment of rule numbers to cellular automata for which and . The values of sites obtained from each of the eight possible three-site neighborhoods are combined to form a binary number that is quoted as a decimal integer. The example shown is for the rule given by Eq. 1.

Further generalizations allow each site in a cellular automaton to take on an arbitrary number of values and allow the value of a site to depend on the values of sites at a distance up to on both sides, so that

The number of different rules with given and grows as and therefore becomes immense even for rather small and .

Figure 8 shows examples of evolution according to some typical rules with various and values. Each rule leads to patterns that differ in detail. However, the examples suggest a very remarkable result: all patterns appear to fall into only four qualitative classes. These basic classes of behavior may be characterized empirically as follows:

• Class 1---evolution leads to a homogeneous state in which, for example, all sites have value 0;
• Class 2---evolution leads to a set of stable or periodic structures that are separated and simple;
• Class 3---evolution leads to a chaotic pattern;
• Class 4---evolution leads to complex structures, sometimes long-lived.

Examples of these classes are indicated in Fig. 8.

[ Figure 8 ] Evolution of some typical cellular automata from disordered initial states. Each group of six patterns shows the evolution of various rules with particular values of and . Sites take on possible values, and the value of a site depends on the values of sites up to sites distant on both sides. Different colors represent different site values: black corresponds to a value of 0, red to 1, green to 2, blue to 3, and yellow to 4. The fact that these and other examples exhibit only four qualitative classes of behavior (see text) suggests considerable universality in the behavior of cellular automata. The examples on page 420 for which are labeled by rule number (in the notation of Fig. 7) and behavior class. The examples on page 420 for which evolve according to rules in which the value of a site depends only on the sum of the values of the sites in its neighborhood on the previous time step. Such rules may be specified by numerical codes such that the coefficient of in the binary decomposition of gives the value attained by a site if its neighborhood had total value on the previous time step. These examples are labeled by code number and behavior class. (I am grateful to R. Pike and J. Condon of Bell Laboratories for their help in preparing these and other color pictures of cellular automata.)

The existence of only four qualitative classes implies considerable universality in the behavior of cellular automata; many features of cellular automata depend only on the class in which they lie and not on the precise details of their evolution. Such universality is analogous, though probably not mathematically related, to the universality found in the equilibrium statistical mechanics of critical phenomena. In that case many systems with quite different detailed construction are found to lie in classes with critical exponents that depend only on general, primarily geometrical features of the systems and not on their detailed construction.

previous  l  next