|
Articles Cellular Automata Cellular Automata as Simple Self-Organizing Systems (1982)
Cellular Automata as Simple Self-Organizing Systems (1982) |
|
Having considered ``ordered'' initial states with only a few nonzero sites, we now turn to ``disordered'' initial states, in which each site is chosen independently to have value 1 with probability 
, giving an initial density 
of nonzero sites.
Figure 4 shows the density of nonzero sites as a function of time in evolution according to three ``complex'' cellular automaton rules from a disordered initial state with 
. For almost all initial densities, the density tends rapidly to a fixed ``equilibrium'' limit (although in the case of rule 90, large fluctuations are apparent even at large times). In a ``mean field'' approximation, the evolution of the density could be estimated by a master equation: however, the presence of non-Markovian effects associated with feedback renders this approach inaccurate in practice. Other methods nevertheless provide exact results for the density in a few cases. One of these cases is rule 90, which exhibits the simplifying feature of ``linear superposition''. Patterns generated from arbitrary initial configurations according to this rule may be obtained by appropriate superpositions (addition modulo two) of displaced copies of the pattern generated from a single initial nonzero site in fig. 3. The number of nonzero sites in the pattern of fig. 3 after 
time steps is equal to the number of odd binomial coefficients in row of Pascal's triangle, and is found by a geometrical method to be (c.f. [10]) 
. Here 
denotes the number of occurrences of the digit 1 in the binary decomposition of the integer 
(thus 
, 
, 
, 
, and so on), and has a very irregular form as a function of . Whenever 
, 
and there are only two nonzero sites in the pattern; the maximum of nonzero sites is achieved when 
. Superposing an initial density 
of these patterns yields an analytical form for the result shown in fig. 4: 
. The additive superposition property of rule 90 is shared by rule 150 (but by no other ``complex'' rules). The density for rule 150 is found to be 
where now 
is a product of factors 
associated with each sequence of 
ones (delimited by zeroes) in the binary decomposition of the integer . is given by the recurrence relation 
where the upper (lower) sign is taken for odd (even), and 
(so that 
, 
and so on).
Figure 5 shows the evolution of a disordered initial state with density 1/2 according to each of the 32 possible elementary cellular automaton rules. As in fig. 3, several classes of behaviour are evident. Rules such as 250 evolve rapidly to uniform states. Rules such as 94 or 132 evolve after a few time steps to stable patterns, sometimes involving several independent sections executing short-period cycles. This behaviour is analogous to that found in dynamical systems with limit points or limit cycles. ``Complex'' rules, such as 18 and 90, yield complicated patterns, analogous to ``strange attractors'' in dynamical systems (e.g. [11]). Although the values of initial sites are statistically uncorrelated, the cellular automaton evolution is seen to generate definite structures. One characteristic of this simple ``self-organization'' is the appearance of long correlated sequences of sites, giving rise to the inverted triangles visible in fig. 5. Triangles of all sizes are found, but their spectrum is exponentially damped. Denoting as before the density of triangles of length by 
, one finds that for large , takes on the universal form 
for all complex rules, and (almost) all initial states. The value of 
is found to be 
for all (complex) rules except the ``linear'' ones 90 and 150, which instead give 
. Once again, therefore, the statistical properties of the patterns generated by cellular automaton evolution are found to exhibit universality, and to be independent of the details of the cellular automaton rule or the initial state.
