The Cook Book
Recipe for the week of June 5 - 11
Rule 30: Wolfram's Pseudo-random Bit Generator
- My favorite candidate for a deterministic random sequence of 0's and
1's is generated by Wolfram's rule 30, the one-dimensional CA with
transitions given by
x(n+1,i) = x(n,i-1) xor [x(n,i) or x(n,i+1)].
Starting from a doubly-infinite completely random sequence x(0,i),
one can show that the time slice at the origin, x(n,0); n>0, is also
completely random. The argument relies on a clever application of
xor to both sides of the above equation, a trick that Wolfram
attributes to Milnor. The Pascal Triangle Mod 2 CA
x(n+1,i) = x(n,i-1) xor x(n,i+1),
which is linear, satisfies the same property. At first glance, it seems
that one is merely trading a random source for random output. The Ergodic
Theorem implies that both rules should generate random time slices starting
from almost every x.
- The difference between the two processes, due to the nonlinear or
operation in rule 30, is that finite configurations of 1's appear to evolve
typically in the former case whereas they certainly do not in the latter.
Starting from a single 1 at the origin, the linear rule generates all 0's
at the origin. One checkerboard subgraph of space-time has all 0's, while
the other makes a Sierpinski Lattice, the discrete version of a fractal
known as the Sierpinksi gasket. In contrast, rule 30 started from a single
1 generates a stream of bits at the origin that performs quite well on all
the standard statistical tests for randomness. Details and lots of pictures
appear in Wolfram, S. (1986) "Random sequence generation by cellular
automata" Advances in Applied Mathematics 7 123-169.
- I used Rudy Rucker's CAPOW, featured last week, to make a soup
of rule 30 started from a single 1. Note the boundary between a more
patterned phase at the left of the triangle and the chaotic phase
surrounding the time slice at the origin. This and many other basic
1d CA dynamics are included with Rucker's package; e.g.. rule 90
makes the Sierpinski lattice described above.