Complexity_ A Guided Tour - Melanie Mitchell [73]
Now, according to Wolfram, since extremely simple rules such as Rule 110 can support universal computation, then most natural systems—presumably more complicated than Rule 110—can probably support universal computation too. And, Wolfram believes, there is nothing more complex than what can be computed by a universal computer, given the right input. Thus there is an upper limit on the complexity of possible computations in nature.
As I described in chapter 4, Alan Turing showed that universal computers can in principle compute anything that is “computable.” However, some computations are simpler than others. Even though they both could run on the same computer, the program “calculate 1 + 1” would result in a less complicated computational process than a program that simulates the earth’s climate, correct? But Wolfram’s principle in fact asserts that, in nature, the “sophistication” of all computations actually being performed is equivalent.
Does any of this make sense? Wolfram’s theories are far from being generally accepted. I’ll give you my own evaluation. As for points 1 and 2, I think Wolfram is on the right track in proposing that simple computer models and experiments can lead to much progress in science, as shown in examples throughout this book. As I’ll describe in chapter 12, I think that one can interpret the behavior of many natural systems in terms of information processing. I also find it plausible that many such systems can support universal computation, though the significance of this for science hasn’t been demonstrated yet.
Regarding point 3, the jury is also still out on whether there are processes in nature that are more powerful than universal computers (i.e., can compute “uncomputable” things). It has been proved that if you could build truly nondigital computers (i.e., that can compute with numbers that have infinitely many decimal places) then you would be able to build such a computer to solve the halting problem, Turing’s uncomputable problem that we saw in chapter 4. Some people, including Wolfram, don’t believe that numbers with infinitely many decimal places actually exist in nature—that is, they think nature is fundamentally digital. There’s no really convincing evidence on either side.
Point 4 makes no sense to me. I find it plausible that my brain can support universal computation (at least as far as my limited memory capacity allows) and that the brain of the worm C. elegans is also (approximately) universal, but I don’t buy the idea that the actual computations we engage in, respectively, are equivalent in sophistication.
Wolfram goes even further in his speculations, and predicts that there is a single, simple cellular automaton-like rule that is the “definite ultimate model for the universe,” the primordial cellular automaton whose computations are the source for everything that exists. How long is this rule? “I’m guessing it’s really very short,” says Wolfram. But how long? “I don’t know. In Mathematica, for example, perhaps three, four lines of code.” Computation writ small.
NKS made a big splash when it was published in 2002—it started out as Amazon.com’s number one bestseller, and remained on the bestseller list for months. Its publication was followed by a large publicity campaign launched by Wolfram Media, the company Wolfram formed to publish his book. Reactions to the book were bipolar: some readers thought it brilliant and revolutionary, others found it self-aggrandizing, arrogant, and lacking in substance and originality (for example, critics pointed out that physicists Konrad Zuse and Edward Fredkin had both theorized that the universe