Review of Wolfram's "A New Kind of Science"

[M Lang / S Railsback]

Here for fun is my colleague John Kadvany's mathematical perspective on
Wolfram's new complexity book. I still have not yet seen the book but
John implies that Wolfram tries to make a strong case for the kind of
work we do with Swarm.

Steve Railsback

Review of Stephen Wolfram's A New Kind of Science (ANKS)

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. address@hidden


-- 
address@hidden
Lang, Railsback & Assoc.
250 California Ave., Arcata CA 95521
707-822-0453; Fax 822-1868


                  ==================================
   Swarm-Modelling is for discussion of Simulation and Modelling techniques
   esp. using Swarm.  For list administration needs (esp. [un]subscribing),
   please send a message to <address@hidden> with "help" in the
   body of the message.
                  ==================================