6. Discussion

This paper represents a first step in the investigation of cellular automata as mathematical models for self-organizing statistical systems. The bulk of the paper consisted in a detailed analysis of elementary cellular automata involving a sequence of sites on a line, with a binary variable at each site evolving in discrete time steps according to the values of its nearest neighbors. Despite the simplicity of their construction, these systems were found to exhibit very complicated behavior.

The 32 possible (legal) elementary cellular automata were found to fall into two broad classes. The first class consisted of simple cellular automata whose time evolution led eventually to simple, usually homogeneous, final states. The second class contained complex cellular automata capable of generating quite complicated structures even from simple initial states. Figure 3 showed the patterns of growth obtained with the very simplest initial state in which only one site had a nonzero value. The complex rules were found to yield self-similar fractal patterns. For all but one of the rules, the patterns exhibited the same fractal dimension (the remaining rule gave a fractal dimension ). With more complicated initial states, the patterns obtained after evolution for many time steps remained self-similar---at least on scales larger than the region of nonzero initial sites. The generation of self-similar patterns was thus found to be a generic feature of complex cellular automata evolving from simple initial states. This result may provide some explanation for the widespread occurrence of self-similarity in natural systems.

Section 3 discussed the evolution of cellular automata from general initial states, in which a finite fraction of the infinite number of initial sites carried value one. Regardless of the initial density of nonzero sites, definite densities were found in the large time limit. Markovian master equation approximations to the density development were found inadequate because of the importance of ''feedback'' in the cellular automaton evolution. Even with disordered or random initial states, in which the values of different sites are statistically uncorrelated, the evolution of complex cellular automata was found to lead to the formation of definite structures, as suggested by Figs. 8 and 15. One characteristic of this self-organization was the generation of long sequences of correlated sites. The spectrum of these sequences was found to reach an equilibrium form after only a few time steps, extending to arbitrarily large scales, but with an exponential damping. The exponents were again found to be universal for all initial states and almost all complex cellular automata (with the exception of two special additive cellular automata).

Any initial cellular automaton state was found to lead at large times to configurations with the same statistical structures. However, in complex cellular automata, the trajectories of almost all specific nearby initial configurations (differing by changes in the values at a few sites) were found to diverge exponentially with time in the phase space of possible configurations. After a few time steps, the mapping from initial to final configurations becomes apparently random (although there are quantitative deviations from a uniform random mapping). Cellular automaton rules may map several initial configurations into the same final configuration, and thus lead to microscopically irreversible time evolution in which trajectories of different states may merge. In the limit of an infinite number of sites, a negligible fraction of all the possible cellular automaton configurations are reached by evolution from any of the possible initial states after a few time steps. Starting even from an ensemble in which each possible configuration appears with equal probability, the cellular automaton evolution concentrates the probabilities for particular configurations, thereby reducing entropy. This phenomenon allows for the possibility of self-organization by enhancing the probabilities of organized configurations and suppressing disorganized configurations.

Many of the qualitative features found for elementary cellular automata appear to survive in more complicated cellular automata (considered briefly in Sec. 5), although several novel phenomena may appear. For example, in one-dimensional cellular automata with three or more possible values at each site, protective membranes may be generated which shield finite regions from the effects of external noise, and allow very regular patterns to grow from small seeds.

Cellular automata may be viewed as computers, with initial configurations considered as input programs and data processed by cellular automaton time evolution. Sufficiently complicated cellular automata are known to be universal computers, capable of computing any computable function given appropriate input. Such cellular automata may be considered as capable of the most complicated behavior conceivable and are presumably capable of simulating any physical system given a suitable input encoding and a sufficiently long running time. In addition, they may be used to simulate the evolution of any other cellular automaton. If the necessary encoding is sufficiently simple, the statistical properties of the simulated cellular automaton should follow those of the universal cellular automaton. Although not capable of universal simulation, simpler cellular automata may often simulate each other. This capability may well form a basis for the universality found in the statistical properties of various cellular automata.

Cellular automata have been developed in this paper as general mathematical models. One may anticipate their application as simple models for a wide variety of natural processes. Their nontrivial features are typically evident only when some form of growth inhibition is present. Examples are found in aggregation processes in which aggregation at a particular point prevents further aggregation at the same point on the next time step.

previous  l  next