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"