A_NEW_KIND_OF_SCIENCE

Mathematica’s First Academic Monograph I f the computer, HAL, from Arthur C. Clark’s 2001: A Space Odyssey were to write an academic mono- graph, you can be sure of two things. (1) It would possess many novel and important ideas because HAL is bril- liant. And (2) it would be perplexingly odd because HAL’s writing style would violate countless social conventions implicitly followed by human writers (the social conventions being particu- larly difficult for HAL to learn). Al- though HAL is fictional, history was made this year—just one year after the fantasy time period for HAL—when Stephen Wolfram rigged up his Math- ematica software to write the first aca- demic monograph ever generated by a computer program. This 1200 page book, titled A New Kind of Science, is indeed what one would expect from HAL: many new and significant ideas, and a chillingly alien, nonhuman pre- sentation style and methodology that gives the reader a unique perspective into what it might be like to be an artificial intelligence. All ribbing aside, it really does seem as if something like Mathematica, not Wolfram, might have written the book: the repetitive- ness, the immodesty, the title, begin- ning nearly every sentence with “and” or “but,” the shortness of the para- graphs, his uncanny ability to refer to figures without numbering them, the utter lack of citations, the frequent use of the phrases “my suspicion is that…” and the quite distinct “my strong sus- picion is that…,” the grandiosity of his conclusions, the fact that there is more text in the endnotes than the main text (350 pages of double column small print), and, most of all, his ability to make all of these quirks seem as if they follow inexorably from some kind of internal book-writing logic. Despite all this, the book is eminently readable and serves as one of the best examples I have ever seen for how complicated ideas can be explained using just prose and (gobs of gorgeous) pictures. We could all learn a thing or two about presentation from his example. As for his thumbing his nose at academic et- iquette—for example, by his lack of ci- tations and references—it seems to me that when you are independently wealthy and self-made, thumbing your nose is your prerogative. Let’s put aside the way Wolfram says what he says. What does he actu- ally say? There are more than a dozen paper’s worth of work presented in the book. I will focus here on Wolfram’s central thesis, his Principle of Compu- tational Equivalence. Some prelimi- naries are needed. Imagine an infinite, linear array of cells all side by side, and suppose that each cell can be either black or white. Now suppose that the color of cells can change through time, and that how any given cell changes its color at the next time step depends only on the color of itself and its two adjacent neighbors. The fact that a cell’s color at the next time step de- pends only on the nearby cells is im- portant, for it makes cellular automata a nice way of modeling physical mech- anisms of all kinds, and is one of the main reasons cellular automata are in- teresting in the first place. The supposition above delimits a class of 256 particularly simple cellular automata rules, which can be classified into four broad types, depending on their behavior (i.e., depending on the manner in which the pattern of cell colors change through time). Type I rules are those that lead only to simple, A NEW KIND OF SCIENCE by Stephen Wolfram, Wolfram Media Inc., Champaign, IL, 2002 1192 pp, $44.95 (US hardcover) Reviews book & software © 2003 Wiley Periodicals, Inc., Vol. 8, No. 2 C O M P L E X I T Y 1 F1 tapraid5/a5-cplx/a5-cplx/a50602/a50030d02o deangeln S�5 1/17/03 22:00 Art: BR-84 Input-DCT-msh repetitive behaviors. Type II rules are those that lead to order, nestedness, and certain fractal-like qualities in the behaviors. Type III rules are those whose behaviors appear to be random, with no long-range correlations at all, and Type IV rules are the interesting rules, those that appear to be suffi- ciently complex that no pattern can be seen in the behaviors, and yet there do appear to be long-range correlations. “Rule 110” is one of these Type IV rules and is the main character in the book. This rule just says the following: take “the new color of a cell to be black in every case except when the previous colors of the cell and its two neighbors were all the same, or when the left neighbor was black and the cell and its right neighbor were both white” (p. 31). Now to the central mathematical result of the book, which concerns the notion of computational universality. A mechanism, or rule, is said to be computationally universal if for each computable function there is some ini- tial condition such that the rule, when acting on that initial condition, is able to compute that function. (In effect, then, the initial condition is a program that computes the function.) As an ex- ample, all modern computers are com- putationally universal, in that for each computable function it is possible to put in inputs (an “initial condition”) to your computer that make your com- puter compute that function, which is just to say that you can buy software (a purchased “initial condition”) whose job it is to compute that function. For cellular automata, the initial condition is the initial colors of all the cells in the linear array, and in the 1970s and 80s it was shown that there were computationally universal cellu- lar automata with nearest-neighbor rules (see Wolfram’s endnote on p. 1115). These were important results, for it meant that nearest-neighbor physical-mechanism-like rules can do anything a computer can do. And these mechanism-like rules are inher- ently more interesting to scientists wishing to model the world’s mecha- nisms; e.g., in biology, a computer is not a good way of thinking about how groups of cells interact, but a cellular automaton is. The computational uni- versality of cellular automata opens up the possibility for computational uni- versality existing in the world (e.g., in groups of cells). But these early com- putationally universal cellular autom- ata rules were very complicated (re- quiring lots of colors, not just black and white), leaving one to doubt whether computational universality could really ever be expected to occur in nature. Wolfram suspected that Rule 110, which is much simpler than the previ- ously known computationally univer- sal cellular automata rules, was com- putationally universal, and— here comes the central mathematical result of the book—a student/assistant of his named Matthew Cook was able to prove it. That is, although Rule 110 is a simple rule, it is sufficiently powerful that, for any computable function, there exists an initial condition of cell colors such that the evolution of the cells amounts to a computation of the function. If computational universality can not only occur for mechanism-like processes, but simple mechanism-like processes, then perhaps computa- tional universality actually occurs in nature! Which brings us to the Principle of Computational Equivalence. The prin- ciple has two parts. The first is that there is a limit to computational power: nothing in the universe can compute anything that is not Turing computable (i.e., computable given a sufficiently large computer). Except for those like Penrose [1] who argue that brains can compute the Turing-un- computable, I suspect few will find this controversial. At any rate, this “com- putational limit” half of the principle is not particularly unique to Wolfram (e.g., see Changizi [2]). What is new is the second half, which concerns the commonness of computational uni- versality: “almost all processes that are not obviously simple can be viewed as computations of equivalent sophisti- cation” (p. 717), and, in particular, “should thus be in effect [computa- tionally] universal” (p. 718). Despite unambiguous writing throughout most of the book, here Wolfram becomes cryptic, and it is accordingly difficult to pin down what he means by this. The best interpretation I have been able to muster is that almost all processes or behaviors that are not obviously simple are due to an underlying rule or mech- anism that is computationally univer- sal. But why should complex-seeming behavior lead us to expect that the un- derlying mechanism is a computation- ally universal one? To help us answer this, consider behavior now in terms of the activities of a Turing machine when run on some input. (A Turing machine can be understood, for our purposes, as a set of rules directing a Turing machine head to move back and forth along a tape, reading and writing. The input to the Turing ma- chine is written on the tape, and the behavior of the Turing machine on that input is the pattern of activities carried out by the head.) It suffices to look at these Turing machine behav- iors, rather than cellular automaton behaviors, because of their computa- tional equivalence (see above). (It is also where I am more comfortable thinking.) Suppose that a Turing ma- chine’s behavior B when implement- ing algorithm A on input x is not obvi- ously simple. What can we conclude about the rules governing this particu- lar Turing machine? That is, what can we conclude about which Turing ma- chine is probably generating behavior B via algorithm A on input x? There are broadly two kinds of Turing machine that could be underlying the behavior. Possibility 1 is that the Turing machine is not a universal Turing machine (i.e., not computationally universal), but is merely a machine that implements al- gorithm A; it is an algorithm-A-Turing- machine, i.e., a machine “hard-wired” to carry out just that algorithm. Possi- bility 2 is that the Turing machine is universal, and happens to have “loaded” on its tape software for computing al- 2 C O M P L E X I T Y © 2003 Wiley Periodicals, Inc. tapraid5/a5-cplx/a5-cplx/a50602/a50030d02o deangeln S�5 1/17/03 22:00 Art: BR-84 Input-DCT-msh gorithm A. Either way, the same algo- rithm is implemented, and the same behavior B is exhibited when x is the input. (In fact, the same is true even if, by “behavior,” we refer the set of all behaviors exhibited by algorithm A over all inputs.) So, which Turing ma- chine probably underlies behavior B? And why should B’s being not obvi- ously simple make Possibility 2 more probable? Wolfram provides no an- swer. One conceivable answer sketch might be that, for biological processes and behaviors, once evolution stum- bles upon a computationally universal mechanism, organisms employing it tend to take over (for reasons analo- gous to the fact that universal comput- ers sit on all our desks, not an array of specialized devices, one for doing arithmetic, one for word processing, etc.). I suspect there may, indeed, be good reasons to expect that computa- tionally universal mechanisms are out there in biology, and certainly the Cook- Wolfram mathematical result discussed above is a significant piece of any argu- ment toward such a conclusion. Reviewed by Mark Changizi, De- partment of Psychological and Brain Sciences, Duke University, Durham, NC 27705; e-mail: changizi@changizi.com. REFERENCES 1. Penrose, R. Shadows of the Mind; Oxford University Press: New York, 1994. 2. Changizi, M.A. Vagueness, rationality and undecidability: a theory of why there is vagueness. Synthese 1999, 120, 345–374. © 2003 Wiley Periodicals, Inc. C O M P L E X I T Y 3 tapraid5/a5-cplx/a5-cplx/a50602/a50030d02o deangeln S�5 1/17/03 22:00 Art: BR-84 Input-DCT-msh