Review of Stephen Wolfram’s “A New Kind of Science”
Jamie Faye Fenton
http://www.fentonia.com/bio/
I have been awaiting the publication of “A New Kind of
Science” for a decade. My anticipation began at an Artificial Life Conference
in
As the years went by, I would occasionally inquire as to the status of this, and was told that it was “in progress.” Finally, in 2000 it became possible to order ANKOS from Amazon and I did so. While I waited I continued to ponder the issues of complexity and the possible nature of the discoveries Wolfram might have made.
Late in May of this year the book arrived and I proceeded to devour it. Fortunately I had several airline journeys to make, and despite the fact that the book doubled the weight of my laptop carry-on, the time went by quickly.
I had a grand time. I love mathematical visualizations, and the book is crammed-full of them. All of them are well designed and rendered in exquisite detail. These illustrations, along with the clear narrative, should enable anyone to learn the basic elements of complexity theory and follow their implications into biology, physics, and computer science.
My experiences attending Artificial Life conferences served me well. The first several chapters recounted much of what I learned at them. In particular, I first learned of Stephen’s work in Cellular Automata theory there, and was delighted to seem it all explained so elegantly in this book. To recap, in a seminal paper from the 1980s, Wolfram enumerated all possible 3-neighbor 2-state one-dimensional cellular automata rules and classified them into the four “Wolfram Categories”. Category one exhibits degenerate behavior, going to solid white or black quickly, Category two shows simple or nested repetition. Category three appears chaotic, while category four shows localized structures that can interact. Of these four categories, the last two are the interesting ones for complexity theory.
Wolfram includes a “Rogues Gallery” of all 256 3/2 1D rules and I had fun classifying them myself using his criterion.
Wolframs main point at the beginning is that complex behavior can emerge from the evaluation of simple rules. This idea has been around for a while – I recall the wonder at discovering this when doing generative video art in the 1970s – and when I first started mixing multi-track music and noticing that a simple rhythm track, bass line, and melody could combine to a pleasing song.
Where Wolfram breaks new ground is in asserting that, with few exceptions, complex behavior only emerges from simple rules. Most people assume that complex phenomena must have complex causes and thus tend to reach for the wrong conceptual tools (or not try at all).
While Wolfram makes this point repeatedly, he does not give this demon a name. For sake of this review, let me call it “The Fallacy of Inherent Complexity” (and hope for a crisper phrase to eventually come into use).
With the Fallacy of Inherent Complexity in mind, Wolfram spends the next 10 years looking for simple rule-based complexity patterns in nature. He weaves an introduction to complexity theory into a travelogue of natural phenomena that illustrate his point.
Wolfram first introduces us to a variety of formalisms used in computational complexity theory and sets the stage for the last chapters. We learn about complexity in numerical computation, multi-dimension CAs, mobile automata, tag systems, networks, Turing machines, and the like.
Complexity can depend on the rule set used and on the initial conditions that the rule set operates upon. This leads to consideration of the role of randomness in complexity. Wolfram describes three types of randomness that are encountered – first is randomness entering the system from outside of it – examples include user response times and radioactive decay. The second type relates to the initial conditions under which the rule system runs. For example, some CAs appear regular when started from a single black cell, and appear random when started from random states. The third type is “inherent randomness” that is generated by the rule evaluation itself. Most computer random number generators use this third technique, perhaps with seeding from the first.
The distinction between class 3 and class 4 CAs can be discerned even when they are started with random data. Generally class 4 CAs converge on a sort of order in which the emergent localized structures appear (resembling those seen from a “simple start”).
Wolfram turns his attention to everyday systems, biology, and then physics. He finds the basic principal of complexity emerging from simple rules popping up all over. One of the reasons he gives for the 10 year delay in publishing is that he could not stop finding his pattern everywhere and did not want to stop looking. The list is long – music and the arts, crystal growth, material science, the differentiation of biological organisms, computational fluid dynamics, chemistry, quantitative finance, and physics.
Physics, which is Wolfram’s métier, gets its own chapter. First he discusses reversible rules for generating complexity, a necessity for a plausible model in Physics. Fortunately there are several simple example rules that demonstrate both complex behavior and reversibility.
Next Wolfram considers the Second Law of Thermodynamics – which apparently contradicts the reversibility described before. This is neatly disposed of by showing that the reason the “arrow of time” does not seem to run backwards is that computing the requisite initial conditions necessary for staging a particular (complex) reverse event is intractable. (These tie in nicely with the notions of computational irreducibility and computational equivalence mentioned later).
Finally, Wolfram presents a “Straw Man” theory for ultimate structure of the universe based on network automata. As the universe executes, arcs form between nodes according to simple (but unspecified) rules. This process can be viewed as forming a “causal network” and each observer, being embedded within, can only perceive slices of. The network has the requisite topology to correspond to relativity and quantum theory. Elementary particles are “tangles” in the underlying network and non-localized threads in the network may be able to account for quantum entanglement effects.
Not having as deep a background in Physics as I would have
liked, I found this section to be the most challenging in the book. I do find
the ideas to be intriguing enough to lead me to learn more and will revise
these observations later. If there is any field where the theoretical
complexity seems overwhelming, it is physics and I wish him well in finding a
simpler underlying model for it all. I also
call attention to an excellent review of ANKOS published in “Quantitative
Physics” on
Wolfram returns to familiar ground for me in the chapter on “Processes of Perception and Analysis”. I read this chapter out of order when, early on, I sought a formal definition of complexity after imagining constructing a “complexity detector” for sweeping through possibilities.
Unfortunately nobody has come up with a solid definition of complexity yet. The “Process” chapter recounts many of the mechanisms that humans and their cultures have evolved to both perceive and analyze phenomena. Generally they do well in recognizing regularity, repetition, and nesting, but break down when confronted with more complex forms.
Still, humans make progress through science and mathematics. I would cite as an example the familiar Mandelbrot set. We understand both the math involved and can instantly recognize it when we see it, even if the particular image is novel.
Ultimately both Wolfram (and his mentor Murray Gell-Mann) concede that the definition of complexity is inherently phenomenological – kind of like the Supreme Court definition of pornography. As Wolfram suggests in his final chapter – there are irreducible limits on the kinds of computations that an observer can do that place a bound on the kinds of perceptions of complexity that are possible.
Wolfram then turns to the task of tying his discoveries back into the mainstreams of computational complexity theory and meta-mathematics. First, Wolfram gives several spectacular illustrations of CAs that do things like compute prime numbers, emulate other CAs, and emulate other forms of abstract automata such as Turing machines. After acquainting us with the concept of Universality, he describes a proof developed under his tutelage showing that, with appropriate initial conditions, a simple rule 110 CA can accomplish universal computation. (This was the most breathtaking moment for me in the entire book). This, plus several other profusely illustrated examples, sets the stage for his claim that Universality is closely connected to Complexity – and that most complex systems are universal as well.
In the last chapter, Wolfram presents “The Principal of Computational Equivalence”. This principal is stated in several ways, and for me, the ultimate unity of this is slowly emerging.
The first way of stating it is to say that all processes (natural and synthetic) can be viewed as computations. This first way seems to me to be a statement about the scope of the (ubiquitous) computational metaphor.
Other stated elements of this principal include “There is a fundamental equivalence between many different kinds of processes” and “almost all processes that are not obviously simple can be viewed as computations of equivalent sophistication”. To me this implies that there may only be a single “band of complexity” in nature – and it seems to follow from Church’s thesis and the notion that the “emulation overhead” involved in simulating one system in another need not be outrageous. Aaronson’s paper mentions a possible counterexample to this – so the validity here may depend on your definition of “equivalent sophistication”.
While one can run on computation in one system or another, or utilize a more or less efficient algorithm, Wolfram suggests that there is an absolute lower bound for a complex process determined by Computational Irreducibility. Computational Irreducibility affects not only the amount of work needed to calculate the next state in a computation but also must determine the cost of establishing the initial conditions as well.
Questions about Computational Irreducibility can exhibit the same characteristics of undecidability as the famous Turing Halting problem and most algorithms needed for analyzing complex systems are shown to have equivalent computational complexity to well-known problems in automata theory. Wolfram also conducted a number of experiments enumerating simple Turing Machines and systems of logic which he illustrates using his superb graphics. I am amazed by his two-page listing of all the axioms of logic and mathematics, his proof that all of basic logic can be derived from a single axiom using only XOR, and his simple proof of Gödel’s theorem based on rule 110. His method of doing experimental meta-mathematics by generative computer sweeps is inspiring (and obviously one of the basic tools of the new science he proposes).
The notes are in-themselves a joy to read – and generally add depth (and a little attribution) to the basic exposition. The index is extensive.
As others have observed, the fundamental omission is the bibliography. Wolfram’s website includes a picture of his library – I only wish there were enough mega-pixels to make out the titles! We can hope that this is remedied on the website in some coherent way – there has already been considerable controversy about “who discovered what when” and I would appreciate a consistent representation of settled attributions.
Reactions
As I hinted before, I thoroughly enjoyed reading this book. It had the effect of both enlightening me and giving me confidence to go forward learning more mathematics. The illustrations are groundbreaking and the narrative was structured in a way that led me to make many discoveries on my own, often just before they were explained to me.
While the new format undoubtedly helped me, and will help others, a part of me missed the traditional notation and format of mathematics publications. While some of this is present in the notes, I sometimes had trouble telling the difference between a proof and a conjecture. Traditional notation would also serve as a Rosetta Stone for me as I tackle other math and physics texts.
Discussion
The Fallacy of
Inherent Complexity
Perhaps the one “take-away” from this book for the general reader is the concept that complex behavior often emerges from the evaluation of simple rules – and that our intuitions that say “complex phenomena must have a complex cause” – are often wrong. Fortunately this point is made early and often – so it has a high probability of sinking in.
This one point is perhaps the most important one to carry over into the general math and science curriculum – as it should free us up to keep seeking answers rather than giving up when we encounter complexity in our lives.
Cryptography and
Complexity
The discussion about “Complexity from Simplicity” made me
think of cryptography and in particular, the design rules used for defining
cryptosystems. For example, symmetrical ciphers like DES use very simple non-linear
transformations and permutations scheduled by the key material. These are
combined together using the principals of “confusion and diffusion” which are
attributed to
My suspicion is that much more of complexity theory is locked away in classified mathematics – and may have been discovered much earlier than it was in the open world. I would be interested in eventually learning the secret history of complexity theory as it is declassified – and hope that, like in general cryptography, much is rediscovered and publicized in the open world.
Phenomenology and
Complexity
Since Complexity has not been formally defined, we are left with what I call the phenomenological definition – which I claim goes something like this: Simple trivial, repetitive, or nested forms are detected and appreciated (at least to a certain level) by the human mind. When the mind is overwhelmed, it goes into a breakdown state where it puts the phenomena into an “inexplicable” category. If something is “purely inexplicable”, it is classified as random. However if part of the mind incompletely senses a pattern and another part registers inexplicability, then it is classified as complex.
While I have nothing beyond intuition to base this on – I do note that complex things seem beautiful while purely random things do not. Perhaps this is why people use the Mandelbrot set as a screen-saver, but can’t stand to listen to white noise coming out of their speakers.
As Wolfram describes in his chapter on perception and analysis, computers can be programmed to sense regularities and to measure randomness. Perhaps both humans and computers can continue to evolve new processes for seeking regularity and demystifying randomness. Irreducibility would continue to limit the ultimate success of this.
Still, if finding a human-independent definition of complexity is possible, it is worth doing. Maybe complexity has the same problem as AI – once something is explained it shifts toward the explicable category and the goal-line moves ever farther away.
This area is intriguing to me and I will keep thinking about it.
Computational
Equivalence
Several aspects of Computational Equivalence seem plausible. The idea that processes are computations makes sense, particularly when you generalize computation to causality. I would also not be surprised if all type 4 CAs (and their equivalents) are universal as well.
The notion that all computations are of equivalent sophistication is muddled by the lack of a definition of sophistication. (The dictionary defines sophistication as the property of having complexity, so we are left in the phenomenological swamp here). This problem has me off thinking about how good and how bad an equivalent computation can be. It seems to me the range is pretty wide – from one written and evaluated in the native system of the universe, running an algorithm which is close to the “irreducibility” limit all the way to pathological cases designed to piss away as much time as possible [which I am sure can be infinite]. Perhaps we can come up with a metric like “entropy”, which seems like a next-door neighbor for what we are trying to do.
The New Kind of
Scientific Method
Among the moments of wonder and originality in ANKOS, the primary discovery within for me is not a particular factoid, but rather it is the shift in worldview and methods explained as a totality. It is a new paradigm plus a new scientific method. This is my interpretation of is meant by a new kind of science – which I propose to call Complexity Science.
A scientific method is about overcoming the limitations of human perception and intuition to derive and validate a model of the actual structure and behavior of nature. Here is what I take to be the basic elements of Wolfram’s method for Complexity Science:
First the investigator conscientiously disclaims the Fallacy of Inherent Complexity. This means that one should keep digging until you uncover the simple principals that underlay complex phenomena. If you really think that it is inherently complex, you will now need to back that claim up.
An ultimately correct model for a particular complex phenomenon should give an account of the rules involved, initial conditions, execution environment, and its proof of computational irreducibility or an explication of its emulation mechanism.
One way to develop such a model is to imagine a rule system, simulate it or reason about it, and seek resemblance with nature; another is to uncover the structure of the execution system. Both approaches can meet in the middle.
The many examples that Wolfram cites of generative complexity across the sciences contain valuable tactical suggestions for investigators.
There will be a metric and a calculus for irreducibility. Proofs of irreducibility will include transliterations from one system to another (with known properties).
Discrete mathematics in general will get more emphasis and mathematical notation will evolve to describe generative patterns more explicitly.
As this science matures, it will acquire a toolbox of principals, methods, and heuristics which will erratically simplify progress.
Teaching about
Complexity
Complexity Theory is an important part of math education and should be part of any progressive curriculum. I would teach it from within a broader program of experimental math. Perhaps Wolfram Research will someday produce a Mathematica for children.
Wolfram’s Earlier
Papers
Most of the mathematics of complexity theory is explained in a collection of Wolfram’s papers from the 1980s entitled “Cellular Automata and Complexity – Collected Papers”. They all follow the conventions of traditional mathematics publications and are a source of references. They are also useful for discerning the difference between what Wolfram thought before his journey and what he learned along the way.
Conclusions
ANKOS is a fascinating introduction to Complexity Theory and its implications in science and mathematics. The shift in paradigm and scientific method it describes has the potential for clarifying many diverse outstanding issues.
Unfortunately much of the early response to this book has involved reactions to perceived hype and arrogance, which has delayed serious discussion of its ideas, whose value can ultimately only be judged in the fullness of time. I intend to participate in this effort by trying them out.
References:
Aaronson, Scott – Book Review – A New Kind of Science, submitted to Quantum Information and Computation, 2002.
http://arxiv.org/PS_cache/quant-ph/pdf/0206/0206089.pdf
Cohn, Henry - A New Kind of Science, by Stephen Wolfram - The Mathematical Association of America Online book review column.
http://www.maa.org/reviews/wolfram.html
Kurzweil, Ray - Reflections on Stephen Wolfram's "A New Kind of Science" http://www.kurzweilai.net/meme/frame.html?main=/articles/art0464.html
Links to additional reviews can be found at: http://www.math.usf.edu/~eclark/ANKOS_reviews.html