|
Articles Computation Theory Random Sequence Generation by Cellular Automata (1986)
Random Sequence Generation by Cellular Automata (1986) |
|
Much of the discussion above has concerned the behaviour of the cellular automaton (3.1) in the idealized limit of an infinite lattice of sites. But practical implementations must use finite size registers, and certain global properties can depend on the size and boundary conditions chosen.
The total number of possible states in a size 
cellular automaton is 
. Evolution between these states can be represented by a finite state transition diagram. Figure 9.1 gives some examples of such diagrams for the cellular automaton of Eq. (3.1) with periodic boundary conditions, as in Eq. (2.2). Table 9.1 summarizes some of their properties. The results are seen to depend not only on the magnitude of , but also presumably on its number theoretical properties.
Each state transition diagram contains a set of cycles, fed by trees representing transients. The cycles may be considered as ``attractors'' to which states in their ``basins of attraction'' irreversibly evolve.
There are many regularities in the structure of the state transition diagrams obtained from Eq. (3.1). The evolution is thus not well-approximated by a random mapping between states.
. The multiplicity and length of each cycle is given, followed by the fraction of initial states which evolve to a longest cycle (size of attractor basin), the total fraction of all 
states which lie on cycles, and the average length of transient before a cycle is reached in evolution from an arbitrary initial state. (Results for 
were obtained by Holly Peck.)A first observation is that most configurations have unique predecessors under the mapping (3.1) (as mentioned for infinite lattices in Section 4), so there is little branching in the state transition diagram. In fact, it can be shown [32] that a configuration has a unique predecessor unless it contains a pair of value zero sites separated by a sequence of 
value one sites (with 
), or unless is divisible by 3, and all sites have value one. In the former case, the configuration has exactly zero or two predecessors; in the latter case, it has three. The numbers of configurations with zero and two predecessors are equal when is not divisible by 3; there are two more with zero predecessors when 
. For large , the number of configurations with zero or two predecessors behaves as [32] 
, where 
is the real root of 
. Since the total number of configurations grows like , the fraction of nodes in the state transition diagram that are branch points thus tends exponentially to zero.
. Each node represents one of the possible length configurations, and is joined by an arc to its successor under the cellular automaton mapping. Transients corresponding to trees in the graph are seen ultimately to evolve to periodic cycles. Some properties of these state transition diagrams are given in Table 9.1. (Graphics by Steve Strassmann.)A second observation is that there are often many identical parts in the state transition diagrams of Table 9.1 and Fig. 9.1. This is largely a consequence of shift invariance. States in a cellular automaton with periodic boundary conditions that are related by shifts (translations) evolve equivalently. Thus, for example, there are often several identical cycles, related by shifts in their configurations. In addition, the periods of the cycles are often divisible by or its factors, since they contain several sequences of configurations related by shifts. The transient trees that feed each of these sequences are then identical.
The evolution of a finite cellular automaton with periodic boundary conditions is equivalent to the evolution of an infinite cellular automaton with a periodic initial configuration. Thus the results on cycle length distributions in Table 9.1 can be considered as inverse to those in Table 6.2 on configurations with given temporal periods. Cycles of lengths corresponding to these temporal periods occur whenever is divisible by the spatial periods of these configurations. Such short cycles are absent if has none of these factors.
For large , the state transition diagrams for Eq. (3.1) appear to be increasingly dominated by a single cycle. This cycle is longer than the others, and its basin of attraction is large enough that most arbitrarily chosen initial states evolve to it. The low degree of branching in the transient trees implies that the points reached from arbitrary initial states should be roughly uniformly distributed around the cycle.
The shorter cycles in Table 9.1 can be considered as related to subsets of states invariant under the cellular automaton rule. With even, for example, configurations which consist of two identical length 
subsequences can evolve only to configurations of the same type. Once such a configuration has been reached, the evolution is ``trapped'' within this subset of configurations, and must yield shorter cycles. (This phenemonon also occurs for cellular automata with essentially trivial rules, such as the shift mapping 
. All states are on cycles in this case. The different cycles correspond to the possible ``necklaces'' with beads of two kinds, which are inequivalent under shifts or rotations. These necklaces in turn correspond to cyclotomic polynomials; there are 
of them, where 
the Euler totient function (e.g., [4]).) In general, there may exist subsets of states with certain special symmetry properties that are preserved by the cellular automaton rule. Initial states with particular, symmetrical, forms can be expected to have these properties, and thus to be trapped in subsets of state space, and to yield short cycles. For example, with 
, a configuration containing a single nonzero site evolves to a length 
cycle, while most initial configurations evolve to the longest cycle, with 
states.
In the infinite size limit, patterns such as that of Fig. 6.1 generated by the cellular automaton of Eq. (3.1) never become periodic. But with a total of sites, a cycle must occur after or less steps. Table 9.2 and Fig. 9.2 give the actual maximal cycle lengths 
found. A roughly exponential increase of with is seen, and a least squares fit to the data of Table 9.2 yields
Note that if the state transition diagram corresponded to an entirely random mapping between the cellular automaton states, then cycles of average length 
would be expected [34]. The cycles actually obtained are significantly longer. The exponent in Eq. (9.1) may be related to the entropy (4.6) as a result of the expansivity or instability of the mapping discussed in Section 5.
If there were very short cycles, then the sequences produced by the cellular automaton would readily be predictable. So if in fact no such prediction can be made by any polynomial time computation, the length of the cycles that occur should in general increase asymptotically faster than polynomial in (cf. [2]). This behaviour is supported by Eq. (9.1).
If indeed the evolution of cellular automata such as (3.1) is computationally irreducible, then a complex computation may always be required to determine for example the lengths of cycles that appear. For in this case, there can effectively be no better way to find the succession of states that occur, except by explicit application of the rule (3.1). One expects in fact that the problem of finding say whether two configurations lie on the same cycle is PSPACE-complete, and so presumably cannot be solved in a time polynomial in , but rather essentially requires a direct simulation of the cellular automaton evolution. (Note that if the lengths of the cycles studied are 
, where both 
and 
are large, then parallel processing is essentially of no avail in this problem.)
While the determination of cycle lengths and structures may be computationally intractable for cellular automata such as (3.1), it should be much easier for linear cases such as (2.4). From the algebraic theory of these systems it is possible to show for example that the maximal cycle length satisfies [20]
where 
states that the integer 
exactly divides 
. Here 
is the multiplicative order function, equal to the minimum integer 
such that 
. This function divides the totient function 
(equal to the number of integers less than which are relatively prime to ), which is maximal for prime . Table 9.2 and Fig. 9.2 give the actual maximal periods found in this case. Equation (9.2) rarely holds as an equality, and the found are usually much shorter than the corresponding ones for the nonlinear rule (3.1).
for the cellular automaton of Eqs. (3.1) (CA30) and (2.4) (CA60) in circular registers of size .
found for the cellular automata of Eqs. (3.1) (CA30) and (2.4) (CA60) in circular registers of size . In the former case, a selection of seeds, including single nonzero sites, were used. In the latter case, maximal length cycles are always obtained with single nonzero site seeds. The results are plotted in Fig. 9.2. (Results for 
were obtained by Holly Peck and Tsutomu Shimomura with an assembly-language program on a Celerity C-1200 computer.)The cycle structures of finite cellular automata depend in detail on the boundary conditions chosen. Table 9.3 gives the maximal cycle lengths found for rules (3.1) and (2.4) with shift register boundary conditions. The results differ substantially from those with periodic boundary conditions given in Table 9.2. One notable feature is the presence of length 
cycles in the linear cellular automaton (2.4) for certain . These correspond to maximal length linear feedback shift registers, and can be identified by a direct algebraic procedure [4].
found for the cellular automata of Eqs. (3.1) (CA30) and (2.4) (CA60) in shift registers of size (with boundary conditions given by Eq. (2.3)).Other boundary conditions may also be considered. Among them are twisted ones, in which the sites 
and 
are negated in Eq. (2.2). The maximum cycle lengths found with such boundary conditions seem typically shorter than in the purely periodic case.
One may in addition consider boundary conditions in which the boundary site values are fixed, rather than being periodically identified. Section 6 (particularly Fig. 6.2) gave some examples of results with such boundary conditions. Different cycles are obtained in different cases; all those investigated nevertheless give maximal cycle lengths shorter than those of Table 9.2 found with periodic boundary conditions.
What has been discussed so far are cycles in complete finite cellular automaton configurations. But in obtaining random sequences one samples single sites. The sequences found could potentially have periods which were sub-multiples of the periods for the complete configuration. For permutive rules such as (3.1) (or (2.4)) this cannot, however, occur.
The state transition diagrams summarized in Table 9.1 give the number of complete -site configurations that can occur at various stages in the evolution of the cellular automaton (3.1). One may also consider the number of single site temporal sequences that can occur. Table 9.4 gives the fraction of the 
possible length 
temporal sequences that are actually generated from any of the possible initial states in a size cellular automaton evolving according to Eq. (3.1) (with periodic boundary conditions). The results are plotted in Fig. 9.3. Whenever 
, all possible sequences seem to be generated. They appear with roughly equal frequencies.
