Randomness
My earlier toy is one example of simple algorithms producing apparently-random patterns; there are plenty of commercial applications of this sort of thing. Wolfram's examples are striking in their simplicity, though.

Cellular Automata

The cellular automaton, even in its simplest form (one dimension, nearest-neighbour influences, binary state) is a fascinating thing. It's worth reading the book if only for the first few chapters, where he looks at the four basic classes of behaviour of these simple algorithms (roughly: degenerate; repeating; random; and complex), and thoroughly explores the way in which these same behaviours -- including surprisingly complex ones -- aren't necessarily restricted to one dimension, or fixed grids, or discrete states, and that "class 4" behaviour seen in rule 110 is about as complex things get. (On which point Kurzweil has something to say).

Computability and Scientific Mathematics

The rule-110 automaton rule is equivalent to a Turing machine. Before I get to that bit, though, there are some general comments on science, which I suppose are the intended justification for the "new kind of science" title.

Science works by suggesting possible explanations for the world, then producing testable scenarios which would confirm or refute the theory. Modern science is all about maths: the explanations are written down in algebra and calculus. Wolfram suggests that equations (and solving by constraints) are only the roughest of guides, and difficult too. Instead, a new calculus: computing.

This is dramatic, although not necessarily new: Church and Turing trod some of this ground a long while ago. Wolfram's case (simply put) is that simple rules can create complex behaviour, and that algorithmic, iterative, computable models are a better fit than traditional math in explaining that complexity. The downside of computability is that those models might be very hard to intuit or derive from everyday behaviour, and he likes a simple approach to finding appropriate models. With fast computers you can simply take a breadth-first sample search of possible algorithms, and look at the pretty pictures they produce. Some of the patterns have obvious real-world parallels.

There's some interesting stuff about biological evolution in here too, and I think it's probably quite close to the mark.

The universal explanation

A unified "theory of everything" has been an attractive goal since the beginning of science (and before, and since). This usually involves a set of descriptions -- mathematically, equations -- which can be said to govern all physical behaviour at a low enough level that even chemistry and biology are explained. Wolfram has an endearingly extreme version of this affliction: that there is a discoverable (and computable?) algorithm "that reproduces sufficiently many different features of the universe, then it becomes extremely likely that this rule is indeed the final and correct one for the whole universe". Furthermore, his suggested method for finding a rule appears to be: exhaustive (or sampled) search across the problem space.

In what furnace was thy brain? There's a name for this: hubris. Or: believe it if you want to; I don't, because the difficulty in computing the large-scale implications of such a rule would limit both its verification and its applicablity. Map, meet Territory.

But, I'm only on page 468; just over half way through the main text...

Update: I finished the book, but the second half was less than enlightening. Around page 516 there's a hint of something interesting in his causal networks model, but the endless verbiage just descends into vagueness. Later, the "principle of computational equivalence" surely doesn't take a whole chapter wherein I couldn't find a single concise definition; a couple of pages should have been more than enough.

One paragraph kept coming back, repeated in very similar forms again and again, like a roomful of class-2 cellular automata at typewriters:

Before the discoveries in this book, one might have thought that to create anything with a significant level of apparent complexity would necessarily require a procedure which itself had significant complexity. But what we have discovered in this book is that in fact there are remarkably simple programs that produce behaviour of great complexity. And what this means -- as the images in this book repeatedly demonstrate -- is that in the end it is rather easy to make pictures for which our visual system can find no simple overall explanation.