Random Walks in Elementary Cellular Automata
This Demonstration illustrates the pseudorandomness capabilities of certain class 3 cellular automata in Wolfram's behavioral classification. For example, the center column of rule 30 appears effectively random and the accumulation of its values apparently produces a random walk. The random walk can be used as a test to tell apart complex from simple behavior. However, some complex class 3 cellular automata are capable of intrinsic randomness starting from the simplest initial configuration (one black cell), such as rule 30 and symmetric rules; other class 3 cellular automata such as rule 22 require some random seed to produce randomness.
The central column (column 0) of rule 30 was for a long time used as the default pseudorandom number generator in Mathematica and it is still available among the various methods to produce pseuorandom numbers in Mathematica. This Demonstration also lets you explore certain properties of the rules listed. For example, the left-hand side evolution of rule 30 displays some transitional regularities and therefore produces a deficient "random walk". However, from one point on, rule 30 starts producing a high-quality random walk just as it would if taking the central column or any other on the right-hand side of its evolution.