Random sequence generation by cellular automata (Q1082817)

A 1-dimensional cellular automaton which generates random sequences is discussed. Each site in the cellular automaton has value 0 or 1, and is updated in parallel according to the rule \[ a_ i'=a_{i-1} XOR (a_ i OR a_{i+1})(a_ i'=(a_{i-1}+a_ i+a_{i+1}+a_ ia_{i+1}) mod 2). \] Despite the simplicity of this rule, the time sequences of site values that it yields seem to be completely random. These sequences are analyzed by a variety of empirical, combinatorial, statistical, dynamical systems theory and computation theory methods. An efficient random sequence generator based on them is suggested.