Recipe for the week of June 5

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.