Wolfram on randomness and RNGs

[Eric Cordian]

Steve Schear writes:

> Stephen Wolfram's book, "A New Kind of Science," is nothing if not 
> interesting.  This encyclopedia-sized volume traces how his fascination 
> with cellular automata, beginning in the 1970s, led him to spend decades 
> exploring the significance of complexity created from simple rules.

I bought a copy the day it came out.  It's an interesting read, but as far
as I can tell, contains nothing of startling import.  It contains not a
single proof.  It merely suggests that Cellular Automata are sufficiently
rich to model any physical process, and maybe someone, someday, will use
them for that purpose.

Then again, so are Turing Machines.

It's much like a book on Cosmology that goes on and on about how lovely
Riemannian Geometry is, and presents lots of beautiful pictures of
manifolds, but leaves it for others to actually figure out a way to use
Riemannian Geometry to model the interaction of geometry and matter.

The one test I usually apply to books is to ask what I can do after
reading them that I couldn't do before reading them.  After Wolfram's
book, I can write the Rule 30 RNG in a couple of lines of the programming
language of my choice.  Not a massive skills increment, but the book does
have some pretty pictures.  Definitely worth $48 if it's in your interest
area, but it's no "Godel, Escher, Bach."

> But the remarkable fact is that none of these 
> methods seem to reveal any real regularities whatsoever in the rule 30 
> cellular automaton sequence. And thus, so far as one can tell, this 
> sequence is at least as random as anything we see in nature.

Yes, but...

A cellular automaton consists of an array of cells in 1-1 correspondence
with the integers, and does a potentially infinite amount of computation
at each step.  It is not particularly striking that we can generate a
seemingly random sequence of bits using an open-ended amount of
computation between emitting each of them.

> But is it truly random?

I get the impression Wolfram believes the universe is not random but
pseudo-random.  His measure of randomness is that there is no shorter
method of computing the random sequence than by running the CA that
generates it.

This gets into the whole descriptional or Kolmogorov complexity idea of
random strings being those that have no shorter description than
themselves.  As opposed to the type of randomness we imagine we get from
things like radioactive decay, which Wolfram no doubt secretly believes
are the result of small scale discrete processes as well.

We hashed some of this around in sci.math when the book came out, and 
someone mentioned that Wolfram was peddling Rule 30 at Crypto '85.

         Article Reference:  (Crypto '85)
         Article:  Cryptography with Cellular Automata
         Author:   Stephen Wolfram

While "A New Kind of Science" contains lots of new and original things,
what's new isn't original, and what's original isn't new.  That Wolfram is
less than candid in disclosing this, and according to some, does not
credit colleagues for their ideas which he borrows, makes the book less
than a stunning exposition of its subject matter.

There's even a 1993 post by Bruce Schneier in sci.crypt commenting on
Rule 30.

  [There is a known plaintext attack against these generators; see
   W. Meier and O. Staffelbach, "An Analysis of Pseudo-Random Sequence
   Generators by Cellular Automata," Advances in Cryptography--EUROCRYPT
   '91 Proceedings, Springer- Verlag, 1991, pp. 186-199.  The attack is
   quite efficient on a PC with values of n (widths of th CA) up to
   500.  Additionally, Paul Bardell proved that the output of a CA is
   identical to the output of a linear-feedback shift register, and is
   hence no more secure.  See: P.H. Bardell, "Analysis of Cellular
   Automata Used as Pseudorandom Pattern Generators," Proceedings of
   1990 International Test Conference, pp. 762-768.]

I'm also not convinced that the Rule 30 bitstream does not have a compact
discription, merely because Wolfram has so far failed to discover one. 

-- 
Eric Michael Cordian 0+
O:.T:.O:. Mathematical Munitions Division
"Do What Thou Wilt Shall Be The Whole Of The Law"