|
Two-Dimensional Cellular Automata (1985) |
|
In this section, we discuss the evolution of cellular automata from disordered initial states, in which each site is randomly chosen to have value zero or one (usually with probability 
). Such disordered configurations are typical members of the set of all possible configurations. Patterns generated from them are thus typical of those obtained with any initial state. The presence of structure in these patterns is an indication of self-organization in the cellular automaton.
, 
, with code 985707700. All nonzero sites are shown black. The initial state contains a single site with value 3. Growth occurs when a site with value 1 appears on the boundary.As mentioned in Section 1, four qualitative classes of behavior have been identified in the evolution of one-dimensional cellular automata from disordered initial states. Examples of these classes are shown in Fig. 12. Figure 13 shows the evolution of some typical two-dimensional cellular automata from disordered initial states. The same four qualitative classes of behavior may again be identified here. In fact, the space-time sections for two-dimensional cellular automata have a striking qualitative similarity to sections obtained from one-dimensional cellular automata, perhaps with some probabilistic noise added.
Just as in one dimension, some two-dimensional cellular automata evolve from almost all initial states to a unique homogeneous state, such as the null configuration. The final state for such class 1 cellular automata is usually reached after just a few time steps, but in some rare cases, there may be a long transient.
Figures 13(a) and 14(a) give an example of a two-dimensional cellular automaton with class-2 behavior. The disordered initial state evolves to a collection of separated simple structures, each stable or oscillatory with a small period. Each of these structures is a remnant of a particular feature in the initial state. The cellular automaton rule acts as a ``filter'' which preserves only certain features of the initial state. There is usually a simple pattern to the set of features preserved, and to the set of persistent structures produced. It should in fact be possible to devise cellular automaton rules that recognize particular sets of features, and to use such class-2 cellular automata for practical image processing tasks (cf. Ref. 25).
The patterns generated by evolution from several different disordered configurations according to a particular cellular automaton rule are almost always qualitatively similar. Yet in many cases the cellular automaton evolution is unstable, in that small changes in the initial state lead to increasing changes in the patterns generated with time. Figures 12 and 13 include difference patterns that illustrate the effect of changing the value of a single site in the initial state. For class-2 cellular automata, such a change affects only a finite region, and the difference pattern remains bounded with time. Information propagates only a finite distance in class-2 cellular automata, so that a particular region of the final state is determined from a bounded region in the initial state. For class-3 cellular automata, on the other hand, information generically propagates at a nonzero speed forever, and a small change in the initial state affects an ever-increasing region. The difference patterns for class-3 cellular automata thus grow without bound, usually at a constant rate.
The locally periodic patterns generated after many time steps by class-2 cellular automata such as in Fig. 13(a) consist of many separated structures located at essentially arbitrary positions. Figure 13(b) shows another form of class-2 cellular automaton. There are four basic ``phases.'' Two phases have vertical stripes, with either on even or odd sites. The other two phases have horizontal stripes. Regions that take on forms corresponding to one of these phases are invariant under the cellular automaton rule. Starting from a typical disordered state, each region in the cellular automaton lattice evolves toward a particular phase. At large times, the cellular automaton thus ``crystallizes'' into a patchwork of ``domains.'' The domains consist of regions in particular phases. They are separated by domain walls. In the example of Fig. 13(b), these domain walls become essentially stationary after a finite time.
), with 
possible values at each site: (a) 
, code 12, (b) 
, code 7530, (c) 
, code 681, (d) 
, code 3250, (e) 
, code 6, (f) , code 348, (g) , code 138, (h) , code 318, (i) , code 792.
A change in a single initial site produces a difference pattern that ultimately spreads only along the domain walls. The spread continues only so long as each successive region on the domain wall contains only particular arrangements of site values. The spread stops if a ``pinning defect,'' corresponding to other arrangements of site values, is encountered. The arrangement of site values on the domain walls may in a first approximation be considered random. The difference pattern will thus spread forever only if the arrangements of site values necessary to support its propagation occur with a probability above the percolation threshold (e.g., Ref. 26), so that they form an infinite connected cluster with probability one.
Phases in cellular automata may in general be described by ``order parameters'' that specify the spatially periodic patterns of sites corresponding to each phase. The size of domains generated by evolution from disordered initial states depends on the length of time before the domains become ``frozen'': slower relaxation leads to larger domains, as in annealing. A final state reached after any finite time can contain only finite size domains, and therefore cannot be a pure phase. States generated by two-dimensional cellular automata may contain ``point'' and ``line'' defects. Point defects are localized regions within domains. An example is the ``L-shaped'' region of zero sites in domains of the value one phase for the cellular automaton illustrated in Fig. 13(e). Line defects correspond to walls separating domains.
In the cellular automaton of Fig. 13(b), the domains become stationary after a few time steps. In the case of Fig. 13(e), however, the domains can continue to move forever, essentially by a diffusion process. Figure 12(d) shows a one-dimensional cellular automaton with domain walls that exhibit analogous behavior (cf. Refs. 27 and 17). In both cases, some domains become progressively larger with time, while others eventually disappear completely. The domain walls in Fig. 13(e) behave as if they carry a positive surface tension (cf. Ref. 28); the diffusion process responsible for their movement is biased to reduce the local curvature of the interface. A linear interface is stable under the cellular automaton rule of Fig. 13(e). In addition, the heights of any protrusions or intrusions cannot increase with time. In general, they decay, often quite slowly, until they are of height at most one. Deformations of height one, analogous to surface waves, do not decay further, and are governed by a one-dimensional cellular automaton rule (with , , and rule number 150). At large times, therefore, a domain must either shrink to zero size, or must have walls with continually decreasing curvatures.
Figure 13(c) shows a two-dimensional cellular automaton with structures analogous to domains walls that carry a negative surface tension. More and more convoluted patterns are obtained with time. The resulting labyrinthine state is strongly reminiscent of behavior observed with ferrofluids or magnetic bubbles.
Figures 13(f), 13(g), and 13(h) are examples of two-dimensional cellular automata that exhibit class-3 behavior. Chaotic aperiodic patterns are obtained at all times. Moreover, the difference patterns resulting from changes in single initial site values expand at a fixed rate forever. A remarkable feature is that in almost all cases (Fig. 13(h) is an exception), the expansion occurs at the same speed in all directions, resulting in an asymptotically circular difference pattern. For some rules, the expansion occurs at maximal speed; but often the speed is about 0.8 times the maximum. When the difference patterns are not exactly circular, they tend to have rounded corners. And even with asymmetrical rules, circular difference patterns are often obtained. A rough analog of this behavior is found in asymmetric one-dimensional cellular automata which generate symmetrical difference patterns. Such behavior is found to become increasingly common as and 
increase, or as the number of independent parameters in the rule 
increases.
An argument based on the central limit theorem suggests an explanation for the appearance of circular difference patterns in two-dimensional class-3 cellular automata. Consider the set of sites corresponding to the neighborhood for a cellular automaton rule. For each site, compute the probability that the value of that site changes after one time step of cellular automaton evolution when the value of the center site is changed, averaged over all possible arrangements of site values in the neighborhood. An approximation to the probability distribution of differences is then obtained as a multiple convolution of this kernel. (This approximation is effectively a linear one, analogous to Huygens' principle in optics.) The number of convolutions performed increases with time. If the number of neighborhood arrangements is sufficiently large, the kernel tends to be quite smooth. Convolutions of the kernel thus tend to a Gaussian form, independent of direction.
Some asymmetric class-3 cellular automata yield difference patterns that expand, say, in the horizontal direction, but contract in the vertical direction. At large times, such cellular automata produce patterns consisting of many independent horizontal lines, each behaving essentially as a one-dimensional class-3 cellular automaton.
Class-3 behavior is considerably the commonest among two-dimensional cellular automata, just as it is for one-dimensional cellular automata with large and . It appears that as the number of parameters or degrees of freedom in a cellular automaton rule increases, there is a higher probability for some degree of freedom to show chaotic behavior, leading to overall chaotic behavior.
Figure 12(i) shows an example of a class-4 one-dimensional cellular automaton. A characteristic feature of class-4 cellular automata is the existence of a complicated set of persistent structures, some of which propagate through space with time. Class-4 rules appear to occur with a frequency of a few per cent among all one-dimensional cellular automaton rules. Often one suspects that some degrees of freedom in a cellular automaton exhibit class-4 behavior, but they are masked by overall chaotic class-3 behavior.
Class-4 cellular automata appear to be much less common in two dimensions than in one dimension. Figures 13(i) and 13(b) show the evolution of a two-dimensional cellular automaton known as the ``Game of Life.''
Many persistent structures, some propagating, have been identified in this cellular automaton. It has in addition been shown that these structures can be combined to perform arbitrary information processing, so that the cellular automaton supports universal computation. Starting from a disordered initial state, the density of propagating structures (``gliders'') produced is about one per 2000 site region.
Except for a few simple variants on the Game of Life, no other definite class-4 two-dimensional cellular automata were found in a random sample of several thousand outer totalistic rules. (5) Some rules that appeared to be of class 2 were found to have long transients, characteristic of class-4 behavior, but no propagating structures were seen. Other rules seemed to exhibit some class-4 features, but they were overwhelmed by dominant class-3 behavior.
