3. Local Properties of Elementary Cellular Automata

We shall examine now the statistical analysis of configurations generated by time evolution of ''elementary'' cellular automata, as illustrated in Figs. 3 and 8. This section considers statistical properties of individual such configurations; Sec. 4 discusses the ensemble of all possible configurations. The primary purpose is to obtain a quantitative characterization of the ''self-organization'' pictorially evident in Fig. 8.

A configuration may be considered disordered (or essentially random) if values at different sites are statistically uncorrelated (and thus behave as ''independent random variables''). Such configurations represent a discrete form of ''white noise.'' Deviations of statistical measures for cellular automaton configurations from their values for corresponding disordered configurations indicate order, and signal the presence of correlations between values at different sites. An (infinite) disordered configuration is specified by a single parameter, the independent probability for each site to have value 1. The description of an ordered configuration requires more parameters.

Figure 10 shows a set of examples of disordered configurations with probabilities , 0.5, and 0.75. Such disordered configurations were used as the initial configurations for the cellular automaton evolution shown in Fig. 8. Qualitative comparison of the configurations obtained by this evolution with the disordered configurations of Fig. 10 strongly suggests that cellular automata indeed generate more ordered configurations, and exhibit a simple form of self-organization.

[ Figure 10 ] Examples of sets of disordered configurations in which each site is chosen to have value 1 with independent probability (a) 0.25, (b) 0.5, and (c) 0.75. Successive lines are independent. The configurations are to be compared with those generated by cellular automaton evolution as shown in Fig. 8.

The simplest statistical quantity with which to characterize a cellular automaton configuration is the average fraction (density) of sites with value 1, denoted by . For a disordered configuration, is given simply by the independent probability for each site to have value 1.

We consider first the density obtained from a disordered configuration by cellular automaton evolution for one time step. When (as in Fig. 8), a disordered configuration contains all eight possible three-site neighborhoods (illustrated in Fig. 1) with equal probability. Applying a cellular automaton rule (specified, say, by a binary sequence , as in Fig. 1) to this initial state for one time step () yields a configuration in which the fraction of sites with value 1 is given simply by the fraction of the eight possible neighborhoods which yield 1 according to the cellular automaton rule. This fraction is given by

where denotes the number of occurrences of the digit in the binary representation of . Hence, for example, and . With cellular automaton rule 182, therefore, the density after the first time step shown in Fig. 8 is if an infinite number of sites is included. The result (3.1) may be generalized to initial states with by using the probabilities , for each of the eight possible three-site neighborhoods (such as 110) shown in Fig. 1, and adding the probabilities for those which yield 1 on application of the cellular automaton rule.

The function will appear several times in the analysis given below. A graph of it for small is given in Fig. 11, and is seen to be highly irregular. For any , is the total number of digits () in the binary representation of , so that . Furthermore, and for , . Finally, one finds that

References to further results are given in McIlroy (1974) and Stolarsky (1977).

We now consider the behavior of the density obtained after time steps in the limit of large . When , correlations induced by cellular automaton evolution invalidate the approach used in Eq. (3.1), although a similar approach may nevertheless be used in deriving statistical approximations, as discussed below.

[ Figure 11 ] The number of occurrences of the binary digit 1 in the binary representation of the integer , , , , and so on]. The function is defined only for integer : values obtained for successive integer have nevertheless been joined by straight lines.

Figure 8 suggests that with some simple rules (such as 0, 32, or 72), any initial configuration evolves ultimately to the null state , although the length of transient varies. For rule 0, it is clear that for all . Similarly, for rule 72, for . For rule 32, infinite transients may occur, but the probability that a nonzero value survives at a particular site for time steps assuming an initial disordered state with is . Rule 254 yields , with a probability for a transient of length . Rule 204 is the ''identity rule,'' which propagates any initial configuration unchanged and yields . The ''disjunctive superposition'' principle for rule 250 discussed in Sec. 2 implies . For rule 50, the ''conjunctive superposition'' principle yields .

Other simple rules serve as ''filters'' for specific initial sequences, yielding final densities proportional to the initial density of the sequences to be selected. For rule 4, the final density is equal to the initial density of 101 sequences, so that . For rule 36, is determined by the density of initial 00100 and sequences and is approximately for .

Exact results for the behavior of with the modulo-two rule 90 may be derived using the additive superposition property discussed in Sec. 2.

Consider first the number of sites with value 1 obtained by evolution according to rule 90 from an initial state containing a single site with value 1, as illustrated in Fig. 3. Geometrical considerations based on Fig. 5 yield the result (6)

where the function gives the number of occurrences of the digit 1 in the binary representation of the integer , as defined above, and is illustrated in Fig. 11. Equation (3.2) may be derived as follows. Consider the figure generated by (the number of digits in the binary representation of ) steps in the construction of Fig. 5. The configuration obtained after time steps of cellular automaton evolution corresponds to a slice through this figure, with a 1 at each point crossed by a line of the figure, and 0 elsewhere. By construction, the slice must lie in the lower half of the figure. Successive digits in the binary representation of determine whether the slice crosses the upper (0) or lower (1) halves of successively smaller triangles. The number of lines of the figure crossed is multiplied by a factor each time the lower half is chosen. The total number of sites with value 1 encountered is then given by a product of the factors of two associated with each 1 digit in the binary representation of . Inspection of Fig. 5 also yields a formula for the positions of all sites with value 1. With the original site at position 0, the positions of sites with value 1 after time steps are given by , where all possible combinations of signs are to be taken, and the correspond to the positions at which the digit 1 appears in the binary representation of , defined so that and .

Equation (3.2) shows that the density averaged over the region of nonzero sites (''light cone'') in the rule 90 evolution of Fig. 3 is given by and does not tend to a definite limit for large . Nevertheless, the time-average density

tends to zero (as expected from the geometrical construction of Fig. 5) like . (7) Results for initial states containing a finite number of sites with value 1 may be obtained by additive superposition. If the initial configuration is one which would be reached by evolution from a single site after, say, time steps, then the resulting density is given by Eq. (3.2) with the replacement . Only a very small fraction of initial configurations may be treated in this way, since evolution from a single site generates only one of the possible configurations in which the maximum separation between nonzero sites is . For small or highly regular initial configurations, results analogous to (3.2) may nevertheless be derived. Statistical results for evolution from disordered initial states may also be derived. Equation (3.2) implies that after exactly time steps, an initial state containing a single nonzero site evolves to a configuration with only two nonzero sites. At this point, the value of a particular site at position is simply the sum modulo two of the initial values of sites at positions and . If we start from a disordered initial configuration, the density at such time steps is thus given by . In general, the value of a site at time step is a sum modulo two of the initial values of sites, which each have value 1 with probability . If each of a set of sites has value 1 with probability , then the probability that the sum of the values at the sites will be odd (equal to 1 modulo two) is

Thus the density of sites with value 1 obtained by evolution for time steps from an initial state with density according to cellular automaton rule 90 is given by

This result is shown as a function of for the case in Fig. 12. For large , , except at a set of points of measure zero, and Eq. (3.3) implies that as for almost all (so long as ).

Cellular automaton rule 150 shares with rule 90 the property of additive superposition. Inspection of the results for rule 150 given in Fig. 3 indicates that the value of a particular site depends on the values of at least three initial sites (this minimum again being achieved when ), so that . Between the exceptional time steps , the for rule 150 tends to be much flatter than that for rule 90 (illustrated in Fig. 12). An exact result may be obtained, but is more complicated than in the case of rule 90. The geometrical construction of Fig. 6 shows that for rule 150, is a product of factors associated with each sequence of ones (delimited by zeroes) in the binary representation of . The function is given by the recurrence relation where the upper (lower) sign is taken for odd (even), and [so that , and so on]. [ thus measures ''sequence correlations'' in .] The density is then given in analogy with Eq. (3.3) by .

[ Figure 12 ] Average density of sites with value 1 obtained by time evolution according to various cellular automaton rules starting from a disordered initial state with . The additivity of the modulo-two rule 90 may be used to derive the exact result (3.2) for . The irregularities appear for time steps at which the value of each site depends on the values of only a few initial sites. For the nonadditive complex rules exemplified by 18 and 182, the values of sites at time step depend on the values of initial sites, and tends smoothly to a definite limit. This limit is independent of the density of the initial disordered state.

Some aspects of the large-time behavior of nonadditive complex cellular automata may be found using a correspondence between nonadditive and additive rules (Grassberger, 1982). Special classes of configurations in nonadditive cellular automata effectively evolve according to additive rules. For example, with the nonadditive complex rule 18, a configuration in which, say, all even-numbered sites have value zero evolves after one time step to a configuration with all odd-numbered sites zero, and with the values of even-numbered sites given by the sums modulo two of their odd-numbered neighbors on the previous time step, just as for the additive rule 90. An arbitrary initial configuration may always be decomposed into a sequence of (perhaps small) ''domains,'' in each of which either all even-numbered sites or all odd-numbered sites have value zero. These domains are then separated by ''domain walls'' or ''kinks.'' The kinks move in the cellular automaton evolution and may annihilate in pairs. The motion of the kinks is determined by the initial configuration; with a disordered initial configuration, the kinks initially follow approximately a random walk, so that their mean displacement increases with time according to (Grassberger, 1982), and the paths of the kinks are fractal curves. This implies that the average kink density decreases through annihilation as if by diffusion processes according to the formula (Grassberger, 1982). Thus after a sufficiently long time all kinks (at least from any finite initial configuration) must annihilate, leaving a configuration whose alternate sites evolve according to the additive cellular automaton rule 90. Each point on the ''front'' formed by the kink paths yields a pattern analogous to Fig. 5. The superposition of such patterns, each diluted by the insertion of alternate zero sites, yields configurations with an average density (Grassberger, 1982). The large number of sites on the ''front'' suppresses the fluctuations found for complete evolution according to additive rule 90. Starting with a disordered configuration of any nonzero density, evolution according to cellular automaton rule 18 therefore yields an asymptotic density . The existence of a universal , independent of initial density , is characteristic of complex cellular automaton rules.

Straightforward transformations on the case of rule 18 above then yield asymptotic densities for the complex nonadditive rules 146, 122, and 126, and an asymptotic density for rule 182, again all independent of the initial density (Grassberger, 1982). No simple domain structure appears with rule 22, and the approach fails. Simulations yield a numerical estimate for evolution from disordered configurations with any nonzero .

Figure 12 shows the behavior of for the complex nonadditive cellular automata 18 and 182 with , and suggests that the final constant values and are approached roughly exponentially with time.

One may compare exact results for limiting densities of cellular automata with approximations obtained from a statistical approach (akin to ''mean-field theory''). As discussed above, cellular automaton evolution generates correlations between values at different sites. Nevertheless, as a simple approximation, one may ignore these correlations, and parametrize all configurations by their average density , or, equivalently, by the probabilities and , assumed independent, for each site to have value 1 and 0, respectively. With this approximation, the time evolution of the density is given by a master equation

The term represents the average fraction of sites whose values change from 0 to 1 in each time step, and the fraction changing from 1 to 0. is the binary specification of a cellular automaton rule, and the binary number with which it is ''masked'' (digitwise conjunction) selects local rules for three-site neighborhoods with appropriate values at the center site. is the vector of probabilities for the possible three-site neighborhoods, assuming each site independently to have value 1 with probability , and to have value 0 with probability . The dot indicates that each element of this vector is to be multiplied by the corresponding digit of the binary sequence, and the results are to be added together. The equilibrium density is achieved when

This condition yields a polynomial equation for and thus for each of the legal cellular automaton rules. For rule 90, the equation is , which has solutions (null state for all time) and . Rule 18 yields the equation , which has the solutions and , together with the irrelevant solution . Rule 182 yields , giving . For rules 90 and 18, these approximate results are close to the exact results 0.5 and 0.25. For rule 182, there is a significant discrepancy from the exact value 0.75. Nevertheless, for all complex cellular automaton rules, it appears that the master equation (3.4) yields equilibrium densities within 10--20% of the exact values. The discrepancies are a reflection of the violation of the Markovian approximation required to derive Eq. (3.4) and thus of the presence of correlations induced by cellular automaton evolution.

In the discussion above, a definite value for the density at each time step was found by averaging over all sites of an infinite cellular automaton. If instead the density is estimated by averaging over blocks containing a finite number of sites , a distribution of density values is obtained. In a disordered state, the central limit theorem ensures that for large , these density estimates follow a Gaussian distribution with standard deviation . Evolution according to any of the complex cellular automaton rules appears accurately to maintain this Gaussian distribution, while shifting its mean as illustrated in Fig. 12. Density in cellular automaton configurations thus obeys the ''law of large numbers.'' Instead of taking many blocks of sites at a single time step, one might estimate the density at ''equilibrium'' by averaging results for a single block over many time steps. For nonadditive complex cellular automaton rules, it appears that these two procedures yield the same limiting results. However, the large fluctuations in average density visible in Fig. 12 at particular time steps for additive rules (90 and 150) would be lost in a time average.

Cellular automaton evolution is supposed to generate correlations between values at different sites. The very simplest measure of these correlations is the two-point correlation function , where the average is taken over all possible positions in the cellular automaton at a fixed time, and takes on values and when the site at position has values 0 and 1, respectively. A disordered configuration involves no correlations between values at different sites and thus gives for . With the single-site initial state of Fig. 3, evolution of complex cellular automata yields configurations with definite periodicities. These periodicities give rise to peaks in . At time step , the largest peaks occur when and the digit corresponding to appears in the binary decomposition of ; smaller peaks occur when , and so on. For the additive cellular automaton rules 90 and 150, a convolution of this result with the correlation function for any initial state gives the form of after evolution for time steps. With these rules, the correlation function obtained by evolution from a disordered initial configuration thus always remains zero. For nonadditive rules, nonzero short-range correlations may nevertheless be generated from disordered initial configurations. The form of for rule 18 at large times is shown in Fig. 13, and is seen to fall roughly exponentially with a correlation length . The existence of a nonzero correlation length in this case is our first indication of the generation of order by cellular automaton evolution.

[ Figure 13 ] Two-point correlation function for configurations generated at large times by evolution according to cellular automaton rule 18 from any disordered initial configuration. is defined as , where the average is taken over all sites of the cellular automaton, and when site has values 1 and 0, respectively. No correlations are present in a disordered configuration, so that for . Evolution according to certain complex cellular automaton rules, such as 18, yield nonzero but exponentially damped correlations.

Figures 3 and 8 show that the evolution of complex cellular automata generates complicated patterns with a distinctive structure. The average density and the two-point correlation function are too coarse as statistical measures to be sensitive to this structure. Individual configurations appear to contain long sequences of correlated sites, punctuated by disordered regions. The two-dimensional picture formed by the succession of configurations in time is characteristically peppered with triangle structures. These triangles are formed when a long sequence of sites which suddenly all attain the same value, as if by a fluctuation, is progressively reduced in length by ''ambient noise.'' Let denote the density of triangles (in position and time) with base length and filled with sites of value . It is convenient to begin by considering the behavior of this density and then to discuss its consequences for the properties of individual configurations, whose long sequences typically correspond to sections through the triangles.

Consider first evolution from a simple initial state containing a single site with value 1. Figure 3 shows that in this case, all complex cellular automata (except rule 150) generate a qualitatively similar pattern, containing many congruent triangles whose bases have lengths . A geometrical construction for the limiting pattern obtained at large times was given in Fig. 5. At each successive stage in the construction, the linear dimensions (base lengths) of the triangles added are halved, and their number is multiplied by a factor 3. In the limit, therefore, , (with ), and hence

[requiring exactly one triangle of size at time step fixes the normalization as ]. The result (3.5) demonstrates that the patterns obtained from complex cellular automata in Fig. 3 not only contain structure on all scales (in the form of triangles of all sizes), but also exhibit a scale invariance or self similarity which implies the same structure on all scales (cf. Mandelbrot, 1982; Willson, 1982). The power law form of the triangle density (3.5) is independent of the absolute scale of .

Self-similar figures on, for example, a plane may in general be characterized as follows. Find the minimum number of squares with side necessary to cover all parts of the figure (all sites with nonzero values in the cellular automaton case). The figure is self-similar or scale invariant if rescaling changes by a constant factor independent of the absolute size of . In this case, , where is defined to be the Hausdorff-Besicovitch or fractal dimension (Mandelbrot, 1977, 1982) of the figure. A figure filling the plane would give , while a line would give . Intermediate values of indicate clustering or intermittency. According to this definition, the cellular automaton pattern of Fig. 5 has fractal dimension .

Figure 6 gives the construction analogous to Fig. 5 for the pattern generated by rule 150 in Fig. 3. In this case, the triangle density satisfies the two-term recurrence relation with, say, and . For large , this yields (in analogy with the Fibonacci series) (8)

where is the ''golden ratio'' which solves the equation . The limiting fractal dimension of the pattern in Fig. 6 generated by cellular automaton rule 150 is thus .

The self similarity of the patterns generated by time evolution with complex cellular automaton rules in Fig. 3 is shared by almost all the configurations appearing at particular time steps and corresponding to lines through the patterns. If the fractal dimension of the two-dimensional patterns is , then the fractal dimension of almost all the individual configurations is . The configurations obtained at, for example, time steps of the form are members of an exceptional set of measure zero, for which no fractal dimension is defined. Almost all configurations generated from a single initial site by complex cellular automaton rules are thus self-similar, and (except for rule 150) are characterized by a fractal dimension . The second form may be deduced directly from the geometrical construction of Fig. 5. For rule 150, the configurations have fractal dimension .

Figure 14 shows patterns generated by evolution with a selection of complex cellular automaton rules from initial states containing a few sites with value 1, extending over a region of size . Comparison with Fig. 3 demonstrates that in most cases the patterns obtained even after many time steps differ from those generated with a single initial site. A few exceptional initial configurations (such as the one used for the first rule 90 example in Fig. 14) coincide with configurations reached by evolution from a single initial site and therefore yield a similar pattern, appropriately shifted in time. In the general case, Fig. 14 suggests that the form of the initial state determines the number of triangles with size , but does not affect the density of triangles with . As a simple example consider the modulo-two rule 90, whose additive superposition property implies that the final pattern obtained from an arbitrary initial state is simply a superposition of the patterns which would be generated from each of the nonzero initial sites in isolation. These latter patterns were shown in Fig. 5, and involve the generation of a triangle of size at time step . The superposition of such patterns yields at time step a triangle of size at least . This conclusion apparently holds also for nonadditive complex cellular automata, so that, in general, for , the density of triangles follows the form (3.5), as for a single site initial state. The patterns thus exhibit self-similarity for features large compared to the intrinsic scale defined by the ''size'' of the initial state. One therefore concludes that patterns which ''grow'' from any simple initial state according to any of the ''complex'' cellular automaton rules (except 150) share the universal feature of self similarity, characterized by a fractal dimension . On this basis, one may then conjecture that given suitable geometry (perhaps in more than one dimension, and possibly with more than three sites in a neighborhood), many of the wide variety of systems found to exhibit self-similar structure (Mandelbrot, 1977, 1982) attain this structure through local processes which follow cellular automaton rules.

[ Figure 14 ] Twenty-five time steps in the evolution of several simple initial configurations according to cellular automaton rules 90, 126, and 218. Configurations generated by rule 90 obey additive superposition (under addition modulo two). The first initial state taken is exceptional for rules 90 and 218, since it occurs in evolution from a single initial site, as shown in Fig. 3, so that the final pattern is a shifted form of that found in Fig. 3. For other initial states, the patterns obtained deviate substantially from those of Fig. 3. However, features with sizes much larger than the extent of the initial state remain unchanged. For complex cellular automaton rules such as 90 and 126, such features share the self-similarity found in Fig. 3.

Having considered the case of simple initial configurations, we now turn to the case of evolution from disordered initial configurations, illustrated in Fig. 8. Figure 15 shows the first 300 time steps in the evolution of cellular automaton 126, starting from a disordered initial state with density . Triangles of all sizes appear to be generated (the largest appearing in the figure has ). Figure 16 shows the density of triangles obtained at large times by evolution according to rule 126 and all of the other complex cellular automaton rules. The figure reveals the remarkable fact that for large , all nonadditive rules yield the same , distinct from that for the additive rules (90 and 150). All the results are well fit by the form

For nonadditive rules , while for the additive rules . The same results are obtained at large times regardless of the density of the initial state. Thus the spectrum of triangles generated by complex cellular automaton evolution is universal, independent both of the details of the initial state, and of the precise cellular automaton rule used.

The behavior (3.8) of the triangle density with disordered initial states is to be contrasted with that of (3.5) for simple initial states. The precise form of an initial state of finite extent affects the pattern generated only at length scales : at larger length scales the pattern takes on a universal self-similar character. A disordered initial state of infinite extent affects the pattern generated at all length scales and for all times. Triangles of all sizes are nevertheless obtained, so that structure is generated on all scales, as suggested by Fig. 15. However, the pattern is not self-similar, but depends on the absolute scale defined by the spacing between sites.

[ Figure 15 ] Configurations obtained by evolution for 300 time steps from an initial disordered configuration with according to cellular automaton rule 126. The fluctuations visible in the form of triangles and apparent at small scales in Fig. 8 are seen here to occur on all scales. The largest triangle in this sample has a base length of 27 sites.

Disordered configurations are defined to involve no statistical correlations between values at different sites. They thus correspond to a discrete form of white noise and yield a flat spatial frequency spectrum. One may also consider ''pseudodisordered'' configurations in which the value of each individual site is chosen randomly, but according to a distribution which yields statistical correlations between different sites, and a nontrivial spatial Fourier spectrum. For example, a Brownian configuration (with spatial frequency spectrum ) is obtained by assigning a value to each site in succession, with a certain probability for the value to differ from one site to the next (as in a random walk). The patterns generated by cellular automaton from such initial configurations may differ from those obtained with disordered (white noise) initial configurations. Complex nonadditive cellular automata evolving from a Brownian initial state yield patterns whose triangle density decreases less rapidly at large than for disordered initial configurations: the ''long-range order'' of the initial state leads to the generation of longer-range fluctuations. In the extreme limit of a homogeneous initial state (such as or ), cellular automaton evolution preserves the homogeneity, and no finite structures are generated.

[ Figure 16 ] Density of triangle structures generated in the evolution of all the possible complex cellular automata from disordered initial configurations with density . Triangles are evident in Figs. 8 and 16. They are formed when a sequence of sites suddenly attain the same value, but the length of the sequence is progressively reduced on subsequent time steps, until the apex of the triangle is reached. The appearance of triangles is a simple indication of self-organization. The triangle density is defined only at integer values of , but these points have been joined in the figure. For large , the triangle densities for all complex cellular automata are seen to tend towards one of two limiting forms. The group tending to the upper curve are the nonadditve complex cellular automata 18, 22, 122, 126, 146, and 182. The additive rules 90 and 150 follow the lower curve. In both cases, falls off exponentially with , in contrast to the power law form found for the self-similar patterns of Figs. 3, 5, and 14.

The appearance of triangles over a series of time steps in the evolution of complex cellular automata from disordered initial states reflects the generation of long sequences of correlated sites in individual cellular automaton configurations. This effect is measured by the ''sequence density'' , defined as the density of sequences of exactly adjacent sites with the same value (bordered by sites with a different value). Thus, for example, gives the density of 100001 sequences. clearly satisfies the sum rule

In a disordered configuration with density , for large . Any sequence longer than two sites in a complex cellular automaton must yield a triangle, leading to the sum rule

Thus the obtained at large times by evolution from a disordered initial state should follow the same exponential form (3.8) as .

Figure 17 shows the sequence density obtained at various time steps in the evolution of rule 126 from a disordered initial state, as illustrated in Fig. 15. At each time step, the for a disordered configuration (illustrated in Fig. 10) with the same average density has been subtracted. The resulting difference vanishes by definition at , but Fig. 17 shows that for , the cellular automaton evolution yields a nonzero difference. After a few time steps, the cellular automaton tends to an equilibrium state containing an excess of long sequences of sites with value 0, and a deficit of short ones. This final equilibrium does not depend on the density of the initial disordered configuration. Starting from any disordered initial state (random noise), repeated application of the local cellular automaton rules is thus seen to generate ordered configurations whose statistical properties, as measured by sequence densities, differ from those of corresponding disordered configurations. The impression of self-organization in individual configurations given by Fig. 8 is thus quantitatively confirmed.

[ Figure 17 ] Density of sequences of exactly successive sites with value 0 (delimited by sites with value 1) in configurations generated by steps in time evolution according to cellular automaton rule 126, starting from an initial disordered state with density . [The function is defined only for integer : points are joined for ease of identification.] At each time step, the density of sequences in a disordered configuration with the same average total density has been subtracted. This difference vanishes for by definition. The nonzero value shown in the figure for is a manifestation of self-organization in the cellular automaton, suggested qualitatively by comparison of Figs. 8 and 10. For large , an equlibrium state is reached, which exhibits an excess of long sequences and a deficit of short ones.

[ Figure 18 ] Configurations generated from a disordered initial state (with ) by the evolution of the complex nonadditive cellular automaton 126, in the presence of noise which causes values obtained at each site to be reversed with probability at every time step. (a) is for (no ''noise''), (b) for , (c) for , and (d) for . As increases, the structure generated is progressively destroyed. No discontinuity in behavior as a function of is found.

As suggested by the sum rule, the for complex cellular automata with disordered initial states follow the exponential behavior (3.7) found for the . Again, the parameter has a universal value for all nonadditive cellular automaton rules and for additive ones. If all configurations of the cellular automata were disordered, then the sequence density would behave at large as and depend on total average density for the configurations. The form (3.5) yields sequence correlations with the same exponential behavior, but with a fixed , universal to all the nonadditive complex cellular automaton rules, and irrespective of the final densities to which they lead. (The universal form may be viewed as corresponding to an ''effective density'' .)

Cellular automata are usually defined to evolve according to definite deterministic local rules. In modelling physical or biological systems it is, however, sometimes convenient to consider cellular automata whose local rules involve probabilistic elements or noise (cf. Griffeath, 1970; Schulman and Seiden, 1978; Gach et al., 1978). The simplest procedure is to prescribe that at each time step the value obtained by application of the deterministic rule at each site is to be reversed with a probability (and with each site treated independently). (If an energy is associated with the reversal of a site, gives the Boltzmann factor corresponding to a finite temperature heat bath.) Figure 18 shows the effects of introducing such noise in the evolution of cellular automaton rule 126. The structures generated are progressively destroyed as increases. Investigation of densities and correlation functions indicates that the transition to disorder is a continuous one, and no phenomenon analogous to a ''phase transition'' is found.

previous  l  next