Review of Stephen Wolfram's A New Kind of Science (ANKS)
June 5, 2002

by John Kadvany
Policy and Decision Science, Menlo Park, CA.
kadvany@aol.com
 

1. What is the scientific research program proposed in ANKS?  Because of Wolfram's prolix prose style (intended to make the book widely readable) and absence of references to current scientific and mathematical literature, it is a bit difficult to pin down. In addition, ANKS addresses mathematics and its foundations, plus natural and social sciences including physics, biology, economics and psychology.  So evaluating all of this 1,000+ page book involves making judgments across a number of disciplines, and Wolfram may have successes in some areas and not others.

Nonetheless, following is an attempt at a simple summation in terms of ANKS's: A) fundamental conjectures or assumptions; B) positive heuristic, or key ideas for generating new models and problem solutions, predictions or explanations of novel facts, or novel explanation of existing known results; C) its inventory of current successes in solving existing problems or predicting, describing or explaining existing natural phenomena.

A1)  Many, if not all, natural processes, including those of perception and analytical thinking, can be thought of as, or effectively are, computations driven by very, very simple algorithms. Biological growth patterns, e. g., at least descriptively, can be seen as being generated by simple algorithms (e.g. expressible in several lines of Wolfram's Mathematica or other code). For classical continuous-time  processes in physics, they may be discretized and represented as computations, or in some cases, discrete algorithms without closed-form solutions may be the only representation possible.

A2)  Many or most of the algorithms at work in nature will turn out to have the computing power of a universal Turing machine (UTM). That is, in principle, their underlying logic is sufficiently strong to represent any computable function or recursively enumerable set.  In this way, most natural processes are like a general programming language. Complexity therefore can be expected to be ubiquitous. Its appearance in all the forms computable by various UTMS should be no surprise (this could be considered a prediction). Our own perceptual and analytical powers are included as part of this scheme as just more computational representations, similarly at the UTM level. Thus is our own knowledge caught up in or by the limits of universal computation.

A3) Wolfram's Principle of Computational Equivalence (PCE) is then that the computing power implicit in most natural processes/algorithms is all the same since they are equivalent to a UTM.  One UTM cannot completely out-simplify or speed up another UTM over all inputs. Hence at certain point we cannot do better than to directly simulate, by running an algorithm, particular instances of the phenomenon/computations we want to describe or predict.  For these processes, it will ultimately be difficult or impossible to accelerate or simplify our understanding through traditional mathematical theories because of lower bounds on computing specific computational trajectories. Also, by PCE, if most processes are equivalent to UTMs, at a certain point everything can look like, or can represent or simulate, most anything else (modulo the real precision possible through actual mechanical or biological computing machines). And all UTM computations will be similarly limited by the logic of computation and undecidability.

A4) Of special note are facts about natural processes having computational trajectories corresponding to undecidabilty in mathematical theories. If natural process P can calculate like a UTM, and since no general algorithm exists to say whether UTM computations eventually gives an answers of many kinds, then P will be similarly undecidable.  Some properties of  P's eventual behavior are unpredictable in principle, though we may asymmetrically observe, or simulate, a result in finite time if it occurs (e.g. the stock market rises above a certain point vs. staying below it forever; a certain pattern of matter eventually occurs in a physical process or not; etc.). There may be computations analogous to Gödel-like undecidable sentences of arithmetic systems, which are neither "provable" nor "refutable" in P. Some statement-observations about long-run behavior are like "Pi-1" statements of number theory because their logical form is of a universal quantifier prefixing a decidable predicate ("For All P computations, simple pattern p does not occur"; cf.: "For All proofs p in number system S, p is not a proof of '0=1'").

B)  The assumptions A1) to A4) are background to a thorough-going computational approach to nature. ANKS specifically sees as inherently limited closed-form or traditional analytical representations of nature. Lots of processes just need to be studied by direct simulation, e.g. using the combined computational-graphical resources of a language like Wolfram's Mathematica.  We should do this because it looks like that's the only/best thing we can do for lots of problems in the natural and social sciences.

C)  It is unclear from the text of ANKS whether any specific existing significant scientific or mathematical problems have been solved, or what, say, biologists, physicists, economists, psychologists, or logicians should expect in particular from AKNS directly or an ANKS research program.  For example, what existing approaches are doomed to fail, or for what new areas does ANKS provide insight?  This is in spite of individual chapters Wolfram devotes to several areas of science. There is considerable optimism and broad speculation in the book, but specifics, especially ones specialists will look for, seem minimal.  If correct, this is probably the book's great weakness. The programmatic ideas appear more detailed for physics, Wolfram's primary scientific expertise, than for other areas.

2.  A simple statement of the core idea of ANKS is that recursively enumerable (r.e.), but non-recursive, computations (like those of common undecidable theories in mathematics like Peano Arithmetic, many kinds of set theory, etc.) occur throughout the natural world, human perception, and thinking.  These r.e. computations will typically be equivalent in computing power to a UTM. Their important property is that one can just carry out the computation, and if certain behavior occurs, you will eventually discover that. But you may never know, in principle, if the behavior is never going to occur. Such r.e. but non-recursive (and universal) sets turn out to be possible through far simpler computational schemes than most may have thought possible. However, arbitrary inputs are allowed for Wolfram's algorithms, and hence their computing power may be disguised through the implicit complexity of arbitrary input strings, numbers, pixels, bits, neural impulses, whatever. These may be Wolfram's real new contribution in ANKS. In any case, the key property of such computations will be that their long-term, eventual behavior may be undecidable, hence unpredictable.

While it's unclear that Wolfram gives substantive real examples of undecidable computations (though lots of illustrations using cellular automata), it is a provocative and bold hypothesis. Nor does he appear to contribute much, if anything, to the ongoing debate over the importance of, say, true Pi-1 sentences not provable in Peano Arithmetic, or ones provable only in set theories assuming axioms of higher infinity, or how these mathematical debates relate to complexity in the natural sciences.

3.  Understanding PCE and its supporting reasoning takes some care, and Wolfram does not do much to carefully state just what PCE means as a research principle.  Just because, say, a plant, follows a growth law that is in principle equivalent to a UTM (its growth rules plus arbitrary inputs give you the UTM), does not mean that there are relevant natural conditions making that happen.  Hence in reality, because of physical constraints, you actually may be able to describe and predict the plant growth in all kinds of ways, including just qualitative behavior due to complex dynamics (e.g. via the geometry of attractors). This is analogous to limiting the kinds of data structures and classes of inputs you compute with Mathematica or any other computing language.  Hence an "arbitrary input" condition appears critical to PCE.  I think one can believe a general form of PCE is true while it may have zero interesting applications in the natural world. That is, in principle, UTMs may be everywhere, but it is an empirical-theoretical problem whether that has the consequences Wolfram is looking for.  The problem is that in the real world, the relevant input strings needed to achieve the power of a UTM may or may not appear in the physical, biological or cognitive settings needed.  (That does not equate to a rejection of the idea of natural computation.)

4.   Wolfram appears not to be aware of criticisms of simplistic computational paradigms in the natural sciences. For example, Brian Goodwin (How the Leopard Changed Its Spots) has argued that while the phenomenology of plant morphology can be simulated well (e.g. via Lindenmayer-style L-system rewrite rules), in the real world, patterns of growth depend on the constraints imposed by surrounding media (air, water, soil, tissue), developmental requirements (e.g. energy transport), and relevant physical and chemical properties of, say, a growing plant bud, or even a human hand.  Simple examples like Fibonacci patterns in nature then appear, but not as the result of the kind of the kind of computation Wolfram and others may envision. Rather, the patterns are the results of more complicated, and somewhat traditional, dynamics. So one has to beware of a fallacy: Just because computation A looks like process P does not mean that P is usefully explained or due to a computation much like A (cf. Kepler's dynamical theories vs. Copernican mathematical rules for planetary orbits). One really cannot avoid the hard work of determining causality through combined empirical and theoretical research combined.

5.   Wolfram has not solved any existing mathematical conjectures on complexity, in particular P=NP (e.g. whether the general "traveling salesman problem" can be solved in time that is a polynomial function of the length of its input; dozens of other practical problems are equivalent and appear to require exponential time).  He speculates on why P=NP might be undecidable, but adds little to existing understanding of one of today's most famous unsolved mathematical problems. He does not refer to the theorem of Baker, Gill and Solovay that there exist formal languages L1 and L2 such that a relativized P=NP can be shown to be true for L1 and false for L2.  This result has widely been taken to imply that many standard approaches used in recursive function theory cannot establish whether P=NP since most techniques relativize across languages; for some it's a symptom of a deeper but unidentified conceptual issue in contemporary mathematics. (As an analogy, it's something like discovering that a Newtonian rule of mechanics is true in one frame of reference and false in another.)

6. The book contains some remarkable computer implementations. This includes short Mathematica code (hence obviously realizable as a real process) for the general enumeration of primitive recursive functions, as well as a Mathematica implementation of the Friedberg-Muchnik priority method used to define incomparable r.e. sets (perfect information about membership in one does not determine membership for the other). Such simple representations and the actual enumerations are amazing, for they usually exist only as thought-experiments in advanced mathematical proofs.  However Wolfram does not indicate whether ANKS has a replacement for the priority method for generating such sets, a long-standing problem in recursion theory, and the graphics do not appear to tell you much.  Such sets of intermediate complexity, Wolfram believes, are anomalies.  But we don't get a big breakthrough on just why "typical" computations are often either trivial or complex (i.e. equivalent to a UTM), but not of intermediate complexity.  Understanding of this kind, or progress on P=NP, would have been the kind of spectacular result promised in the publicity heralding the release of ANKS.

7. The book includes perhaps unnecessarily long discussions of the equivalence of simple cellular automata with UTMs of various flavors. Wolfram seems in the main "lay reader" text to be presenting these equivalence results as some kind of novelty. His examples of very simple cellular automata which can calculate as UTMs appear to be new and are certainly interesting.  However, the equivalence of various computational approaches (e.g. traditional "tape and machine head" style UTMs, register machines) is well-known and elementary. Wolfram highlights less popular approaches to computation such as combinatory logic, perhaps because of their role in Mathematica. Wolfram basically verifies Church's thesis (that all traditional computation models end up calculating the same class of functions, namely those of UTMs) while adding the important idea that computations are ubiquitous in nature; they are not merely human artifacts.  As in other parts of the book, it's hard here to see: (a) what's a new idea; (b) what's a new version of an existing idea; and most importantly, (c) what the really new consequences are of putting it all together in this way.  There's some of (a), lots of (b), and maybe something of (c).

8.   These equivalence proofs and discussions are not made clearer by the extended prose discussions lacking almost any mathematical notation, symbolism , or equations. The graphical output of Mathematica-implemented cellular automata is the lingua franca for ANKS.  I do not see this single format as so useful. Cellular automata are fine, up to a point. But the graphics in ANKS often are uninformative and repetitive.  An interesting aspect of complexity is how many different mathematical ideas can be related to one another not just through automata theory, but number theory, dynamical systems, geometry, logic, topology, set theory, etc. Much of that flavor and its importance, especially in such a broad-ranging book, is lost by avoiding a more traditional mathematical expository style (cf. successful books for general audiences including Courant-Robbins, What is Mathematics? and Davis-Hersh, The Mathematical Experience).

9.  There is discussion of the so-called problem of free will, SETI (Search for Extra-Terrestrial Intelligence) and wide-ranging speculation about the importance of ANKS to psychology, biology, physics and economics.  Not much of this appears to contribute greatly to existing debates or problems (if they did, they likely would be highlighted or specific literature cited; as indicated above, Wolfram's ideas for physics are more definite than for other areas), nor to create clear directions for interesting future research associated with problems of complexity. Here are examples where one might expect something interesting of ANKS:

Biology: What does ANKS say or imply about scaling laws in nature, and the relationship between organism size and complexity, or the appearance of "typical" exponents in scaling laws?  Fractal forms appear often in nature because they are maximizing, e.g., a surface area exposure for gas exchange in the lungs. Does ANKS provide new or simpler models of such optimal form?
Economics: What does ANKS say about the well-known "heavy tails" of empirical growth rates in finance (i.e. price is not strictly lognormal; the heavy tails are in log(price) or the growth rate), and the earlier approaches to financial self-scaling proposed by Mandelbrot (incidentally an early proponent of "phenomenological" computation as an answer to complexity)?
Psychology: A huge literature exists on specific computational approaches to, say, vision and linguistics.  What does ANKS tell us?  For example, in most cases these computations do not look like UTMs, but are computationally simple, if intricate, once discovered. It's a matter of finding the right ones, figuring out how they are realized (either cognitively or through the brain and nervous system), and how they link together.  For example, linguists can be afraid that a proposed grammar will be too powerful and hence generate way beyond the class of grammatical sentences. An important aspect of the computational model of mind for some (e.g. David Marr, Steven Pinker) is that you need very different kinds of computation for different cognitive tasks; the mind does not at all look like a bunch of cellular automata (or any other single computational model), except at a level of generality used primarily in philosophical arguments. Real cognitive tasks mean real constraints on computing power and algorithm design, which means important features can actually be predicted. The computational theory of mind crowd (e.g. Marr, Putnam, Fodor, Pinker, Dennett, Minsky et al.) has debated natural computation for many years now, so one might have expected a clearer connection between ANKS and their research.

10.  Wolfram discusses most all the key areas of complexity theory, but does not tie them all together in a substantive way. Nobody has yet.  These areas include at least the following:

Combinatorial complexity and P=NP (a la Cook, Karp et al.)
Dynamical systems theory (a la Feigenbaum, Smale, Poincaré et al)
Fractal geometry (classical topologists, Mandelbrot et al)
Proof theory and undecidability of "natural" mathematical statements (a la Paris-Harrington, Kirby-Paris, Friedman, et al)
Combinatorial complexity and the countable infinite (above plus Goodstein, Gentzen, Feferman and others' approaches to proof-theoretic ordinals)
Real versus integer computation (Blum, Cucker, Shub, Smale et al).

Much theoretical work ties proper subsets of these together, but there are still large gaps between combinatorics, the countable infinite, and dynamical systems approaches to complexity.  The Gödel or Einstein who can tie these together by eliminating some tacit "ether" or mistaken conception about computation may be waiting in the wings. But it is not Wolfram and ANKS.

11.   In applying ANKS to mathematics itself, mathematical systems are seen by Wolfram as largely conventional and historical choices possible among formal systems, thought of as computations. There's nothing fundamentally special, from this perspective, about any axiom system in an ultimate sense, nor even the categories of true and false (they are just designated ending states of computations). Wolfram's ideas about mathematical epistemology are probably consistent with lots of pragmatist ideas about today (Putnam, Rorty) and may appear controversial because much philosophy of mathematics is wedded to out-dated philosophical ideas.  But detailed historical approaches to the growth of mathematics, and accounts of real, informal mathematics, have been around for a while, e.g. Imre Lakatos' Proofs and Refutations: The Logic of Mathematical Discovery.  What Wolfram misses is that "historical" choice in science or math does not equate to "arbitrary," as the computational analogy suggests. The primary mathematical abstraction used is just propositional logic, with axiom systems considered as meaningless cellular automata patterns instead of as formalist meaningless formal symbols,. There is even little or no role here for the semantical interpretation of formal systems such as in first-order predicate logic and its model theory.

12. On a personal note, I was very much looking forward to the publication of ANKS.  The book has been promoted for years and its appearance was accompanied by a great deal of publicity. I am a Mathematica user and believe it is a great tool.  (For example, Stan Wagon's book Mathematica in Action contains incredible applications, such as a computational-graphic version of a modified Banach-Tarski paradox, Hilbert and Peano curves, etc.)  But I also believe:

The "informal" prose of ANKS does not make the ideas more accessible. Rather, it makes the few interesting ideas in ANKS hard to find and pin down; The notes, which form a large part of the book, are nicely done, but for the most part appear not to provide much new information for people with modest expertise in the areas of interest (there is lots of nice Mathematica code, however); There is more between heaven and earth than cellular automata; Wolfram's key ideas about ubiquitous universal computation may eventually make contact with empirical science but work remains to be done; The absence of definite references to mathematical and scientific literature, or at least specific problems or controversies, and the apparent lack of traditional (even informal) peer editing or review, will make it harder, not easier, for Wolfram to promote scientific dialogue about, and criticism of, his considerable work.

John Kadvany
Policy and Decision Science, Menlo Park, CA. (kadvany@aol.com)