|
Articles Mathematics Random Sequence Generation by Cellular Automata (1986)
Random Sequence Generation by Cellular Automata (1986) |
|
Sections 4 and 5 have discussed some properties of the patterns produced by evolution according to Eq. (3.1) from generic initial conditions. This section considers evolution from particular special initial configurations.
Figure 6.1 shows on two scales the pattern produced by evolution from a configuration containing a single nonzero site. (This could be considered a difference pattern for the special time-invariant state in which all sites have value zero.) Remarkable complexity is evident.
There are however some definite regularities. For example, diagonal sequences of sites on the left-hand side of the pattern are periodic, with small periods. In general, the value of a site at a depth 
from the edge of the pattern depends only on sites at depths or less; all the other sites on which it could depend always have value 0 because of the initial conditions given. As a consequence, the sites down to depth are independent of those deeper in the pattern, and in fact follow a shifted version of the cellular automaton rule (3.1), with boundary conditions that constrain two sites at one end to have value zero. Since such a finite cellular automaton has a total of 
possible states, any time sequence of values in it must have a period of at most . The corresponding diagonal sequences in the pattern of Fig. 6.1 must therefore also have periods not greater than .
Table 6.1 gives the actual periods of diagonal sequences found at various depths on the left- and right-hand sides of the pattern in Fig. 6.1. These are compared with those for the self-similar pattern shown in Fig. 2.2 generated by evolution according to the linear cellular automaton rule (2.4).
The short periods on the left-hand side of the pattern in Fig. 6.1 are related to the high degree of irreversibility in the effective cellular automaton rule for diagonal sequences in this case [27]. Starting with any possible initial configuration, this cellular automaton always yields cycles with period 
. The maximum value of 
increases very slowly with , yielding maximum cycle lengths which increase in jumps, on average slower than linearly with . (Between the values at which the maximum cycle length increases, a single additional cycle of maximal length seems to be added each time increases by one. The total number of cycle states thus increases at most quadratically with , implying an increasing degree of irreversibility.) The actual sequences that occur near the left-hand boundary of the pattern in Fig. 6.1 correspond to a particular set of those possible in this effective cellular automaton. In a first approximation, they can be considered uniformly distributed among possible -site configurations, and their periods increase very slowly with .
and 
signify
respectively periods for diagonal sequences on the right and left of the patterns, at the specified depth.
(The entries
left blank were not found.)The effective rule for the right-hand side diagonal pattern in Fig. 6.1 is a shifted version of Eq. (3.1)
with boundary conditions
This system is exactly reversible: all of its possible configurations have unique predecessors. All the configurations thus lie on cycles, and again the cycles have periods of the form . Figure 6.2 shows the lengths of longest cycles as a function of . These lengths increase roughly exponentially with ; a least squares fit to the data of Fig. 6.2 yields
This length is small compared to the total number of states ; few states in fact lie on such longest cycles. Nevertheless, the periods of the right-hand diagonal sequences in Fig. 6.1 do seem to increase roughly exponentially with depth, as suggested by Table 6.1.
for the effective cellular automaton which gives the right-hand diagonal
sequences in
Fig. 6.1 down to depth . Points plotted at integer are joined for pictorial purposes.The boundary in Fig. 6.1 between regular behaviour on the left and irregular behaviour on the right seems to be asymptotically linear, and to move to the left with speed 
. A statistical argument for this result can be given in analogy with that for Eq. (5.2). Each site at depth 
on the left-hand side of the pattern could in principle be affected by sites down to depth arbitrarily far up in the pattern. In practice, however, it is unaffected by changes in sites outside a cone whose boundary propagates at speed 
. Thus the irregularity on the right spreads to the left only at this speed.
While diagonal sequences at angles 
in Fig. 6.1 must ultimately become periodic, sequences closer to the vertical need not. In fact, no periodicity has been found in any such sequences. The center vertical (i.e., temporal) sequence has, for example, been tested up to length 
, and no periodicity is seen. One can prove in fact that only one such vertical sequence (obtained from any initial state containing a finite number of nonzero sites) can possibly be periodic [22]. For if two sequences were both periodic, then it would follow that all sequences to their right must also be, which would lead to a contradiction at the edge of the pattern.
Not only has no periodicity been detected in the center vertical sequence of Fig. 6.1; the sequence has also passed all other statistical tests of randomness applied to it, as discussed in Section 10.
While individual sequences seem random, there are local regularities in the overall pattern of Fig. 6.1. Examples are the triangular regions of zero sites. Such regularities are associated with invariants of the cellular automaton rule.
The particular configuration in which all sites have value 0 is invariant under the cellular automaton rule of Eq. (3.1). As a consequence, any string of zeroes that appears can be corrupted only by effects that propagate in from its ends. Thus each string of zeroes that is produced leads to a uniform triangular region.
Table 6.2 and Fig. 6.3 give other configurations which are periodic under the rule (3.1). (They can be considered as invariant under iterations of the rule.) Again, any string that contains just the sequences in these configurations can be corrupted only through end effects, and leads to a regular region in spacetime patterns generated by Eq. (3.1).
In general, there is a finite set of configurations with any particular period 
under a permutive cellular automaton rule such as (3.1). The configurations may be found by starting with a candidate length 
string, then testing whether this and the string it yields through Eq. (3.3) on the left are in fact invariant under 
. The string to be tested need never be longer than 
, since such a string can contain all possible length strings. Thus the periodic configurations consist of repetitions of blocks containing or less site values. (For an arbitrary cellular automaton rule, the set of invariant configurations forms a finite complement language which contains in general an infinite number of sequences with the constraint that certain blocks are excluded [16].)
The pattern in Fig. 6.1 can be considered the effect of a single site ``defect'' in the periodic pattern resulting from a configuration with all sites 0. Figure 6.4 shows difference patterns produced by single site defects in the other periodic configurations of Table 6.2 and Fig. 6.3.
The periodic configurations of Table 6.2 and Fig. 6.3 can be viewed as special states in which the cellular automaton of Eq. (3.1) behaves just like the identity rule. Concatenations of other blocks could simulate other cellular automata: one block might correspond to a value 0 site, and another to a value 1 site in the effective cellular automaton. Some cellular automata (such as that of Eq. (2.4)) simulate themselves under such ``blocking transformations,'' and thus evolve to self-similar patterns. The cellular automata of Eqs. (3.1) and (3.2) are unique among 
, 
rules in simulating no other rules, at least with blocks of length up to eight [14].
