3. A Random Sequence Generator

There are a total of cellular automaton rules that depend on three sites, each with two possible values (, ). Among these are several linear rules similar to that of Eq. (2.4). But the two rules that seem best as random sequence generators are nonlinear, and are given by

or, equivalently,

(rule number 30 [17]; equivalent to rule 86 under reflection), and

or

(rule 45; reflection equivalent to rule 75). Here stands for exclusive disjunction (addition modulo two); for inclusive disjunction (Boolean addition), and for negation. The patterns obtained by evolution from a single nonzero site with each of these rules were shown in Fig. 2.2. It is indeed remarkable that such complexity can arise in systems of such simple construction. A first indication of their potential for random sequence generation is the apparent randomness of the center vertical column of values in the patterns of Fig. 2.2.

This paper concentrates on the cellular automaton of Eq. (3.1). The methods used carry over directly to the cellular automaton of Eq. (3.2), but some of the results obtained in this case are slightly less favourable for random sequence generation.

The cellular automaton rule (3.1) is essentially nonlinear. Nevertheless, its dependence on is in fact linear. This feature (termed ''left permutivity'' in [21], and also studied in [22]) is the basis for many of its properties. In the form (3.1), the rule gives the new value of a site in terms of the old values , and . But the linear dependence on allows the rule to be rewritten as

giving in terms of , and . This relation implies that the spacetime patterns shown, for example, in Figs. 2.1 and 2.2 can be found not only by direct time evolution according to (3.1) from a given initial configuration, but also by extending spatially according to (3.3), starting with the temporal sequence of values of two adjacent sites.

Random sequences are obtained from (3.1) by sampling the values that a particular site attains as a function of time. In practical implementations, a finite number of sites are considered, and are typically arranged in a circular register. Given almost any initial ''seed'' configuration for the sites in the register, a long and seemingly random sequence can apparently be obtained. This paper discusses several approaches to the analysis of the cellular automaton (3.1) and the sequences it produces. While little can rigourously be proved, the overwhelming weight of evidence is that the sequences indeed have a high degree of randomness.

previous  l  next