Notes

(1) The discussion here concentrates on systems first order in time; a more general case is mentioned briefly in Sec. 4.

(2) The quiescence condition is required in many applications to forbid ''instantaneous propagation'' of value-one sites. The reflection symmetry condition guarantees isotropy as well as homogeneity in cellular automaton evolution.

(3) The values of a sequence of (typically 32) sites are represented by bits in a single computer word. Copies of this word shifted one bit to the left and one bit to the right are obtained. Then the cellular automaton rule may be applied in parallel to all bits in the words using single machine instructions for each word-wise Boolean operation. An analogous procedure is convenient in simulation of two-dimensional cellular automata on computer systems with memory-mapped displays, for which application of identical Boolean operations to each display pixel is usually implemented in hardware or firmware.

(4) Here and elsewhere a standard linear congruential pseudorandom number generator with recurrence relation was used. Results were also obtained using other pseudorandom number generation procedures and using random numbers derived from real-time properties of a time-shared computer system.

(5) This similarity may be used as the basis for a simple hardware implementation of one-dimensional cellular automata (Pearson et al., 1981; Hoogland et al., 1982; Toffoli, 1983).

(6) This result has also been derived by somewhat lengthy algebraic means in Glaisher (1899), Fine (1947), Roberts (1957), Kimball et al. (1958), and Honsberger (1976).

(7) This form is strictly correct only for . For , there is a correction factor , which lies between 0.86 and 1, with a broad minimum around .

(8) For small , the triangle density in this case does not behave as a pure power of . Whereas the solution to any one-term recurrence relation, of the type found for cellular automaton rule 90, is a pure power, the solution to a -term recurrence relation is in general a sum of powers, with each exponent given by a root of the characteristic polynomial equation. In the high-order limit, the solutions are dominated by the term with the highest exponent (corresponding to the largest root of the equation). Complex roots yield oscillatory behavior [as in ; , ].

(9) An alternative specification would take each configuration to correspond to one of the vertices of an -dimensional hypercube, labeled by coordinates corresponding to the values of the sites. Points corresponding to configurations differing by values at a single site are then separated by a unit distance in -dimensional space.

(10) The existence of unreachable or ''garden-of-Eden'' configurations in cellular automata is discussed in Moore (1962) and Aggarwal (1973), where criteria (equivalent to irreversibility) for their occurrence are given.

(11) Reversible cellular automata may be constructed in two (or more) dimensions by allowing arbitrary evolution along a line, but generating a sequence of copies (''history'') in the orthogonal direction of the configurations on the line at each time step (Toffoli, 1977a, 1980).

(12) For example, evolution from a pair of successive configurations containing zero and one nonzero sites according to the reversible analog of rule 150 yields a self-similar pattern with fractal dimension .

(13) The result is therefore to be contrasted with the behavior of linear feedback shift registers, analogous to cellular automata except for end effects, in which cycles (de Bruijn sequences) of period may occur (e.g., Golomb, 1967; Berlekamp, 1968).

(14) In the case , neighborhoods of types I and II are known as von Neumann and Moore neighborhoods, respectively.

(15) An analogous result holds for all modulo- rules with prime by virtue of the relation , valid for all primes . The relation is a special case of the general result (Knuth, 1973, Sec. 1.2.6, Ex. 10)

previous