Dr. Dobb's Journal September 2002
Last month, I wrote about Stephen Wolfram's big book, A New Kind of Science (Wolfram Media 2002; ISBN 1-57955-008-8) and concluded by saying that I would have to study Wolfram's Principle of Computational Equivalence further and, if I figured it out, discuss it here this month. I fear that what I meant was that I would figure out exactly what Wolfram was getting at with this Principle and what all the implications of this Principle are, and that I would explain it all succinctly and entertainingly here in 2700 words or less. If that's what I meant, I have to confess failure.
Here's what I can do: I can summarize what Wolfram says about computational equivalence and computational universality and the universe as computation and whether the universe is continuous or discrete, and provide some context on some of these issues. But as to how important or even how original Wolfram's Principle is, my ego is not big enough to think that I have the answers.
Besides, I have to devote some of this month's column space to a couple of other obsessions. In my continuing thread on quantum computing, I'll touch on computational universality as it pertains to the possibility of building quantum computers. And just in case you were wondering, I'll answer the question, whatever happened to Turbo Basic?
Wolfram spends 700 pages building up to this Principle of Computational Equivalence. He thinks it's hugely important, and isn't reticent about saying so. Here is Wolfram's Principle of Computational Equivalence, stated in what he says are the most general terms: "[A]lmost all processes that are not obviously simple can be viewed as computations of equivalent sophistication."
Several ideas are packed into this simple-sounding statement. First, there is the claim that all processes can be viewed as computations. Among DDJ readers, that claim is probably not terribly contentious. We are not put off by the notion that DNA performs computations, or that certain physical processes "compute" a fast Fourier transform. But Wolfram does mean all processes — analytical thought, perception, biological evolution, and the unfolding of the universe since the Big Bang, to name a few.
Second, the implicit message that this is a productive, probably the most productive, way of looking at things. That scientific inquiry ought to involve, in a much greater sense than it has in the past, the search for the program behind the process. Again, not obviously heretical. Science has generally meant a search for general laws rather than detailed programs, but most scientists today would probably agree with a statement along the lines of "Computer simulations of natural processes can be a useful tool for the advancement of scientific understanding." Most would probably not go along with Wolfram's view that science before Stephen Wolfram and his new kind of computation-centric science has just been picking the low-hanging fruit off the tree of knowledge.
Third, discreteness: Discrete and continuous models of the universe have battled for supremacy since before Plato's time, and Wolfram comes down on the side of the atomists. This definitely is controversial. He does supply examples of continuous programs in his book and he does take pains to show that discreteness is not a necessary feature of the cellular automata examples that he uses to make his points. But nearly all the cellular automata in the book are discrete. In these cellular automata, discrete cells in a discrete grid-like space nudge their neighbors into discrete changes of state in discrete time increments. Ultimately, Wolfram makes it clear that he doubts that continuous mathematical functions have any connection with physical reality, and suspects that space is not a continuum, but rather something discrete. Probably not a cellular automata-style grid, but maybe a network. And time: "There is nothing to say that on shorter scales, time is not discrete." Wolfram would find it convenient if the cosmic clockworks were shown to be digital. He dances around the discrete/continuous issue for a while, but eventually commits himself: "[M]y strong, strong suspicion is that at a fundamental level, absolutely every aspect of our universe will in the end turn out to be discrete." This is certainly not mainstream scientific thinking.
Fourth, Wolfram's criterion of "obviously simple" is a very low threshold. Absurdly simple cellular automata with trivial initial conditions are sometimes complex enough to clear the bar. It was confronting these apparently simple programs that generate apparently infinitely complex output that set Wolfram off on the 20-year research program that culminated in A New Kind of Science.
Fifth, the "equivalent sophistication" part. He's saying that, in some sense, there is no fundamental difference between a Rule-30 cellular automaton and a human mind, or between a hurricane and the entire universe.
They are all computations of equivalent sophistication. Not just in some sense, but in a very important sense: All such processes are computationally equivalent, meaning that they all have the same fundamental limits. The human mind is capable of the same set of computations as a dust cloud or a banana slug — and no more.
In A New Kind of Science, Wolfram describes the simple programs that caught his attention so dramatically two decades ago. He shows how they can produce output of unlimited complexity, that in fact, they can be universal computers. He shows how they can be made to mirror processes in nature, the form and structure of living things, turbulent fluids, economic behavior. He asserts that these processes are also effectively universal computers. And he asserts that all of these things are computationally equivalent — that there is really only one level of computational capability beyond the trivial. It's sort of a You Got It or You Don't Got It thing, and all these processes have got it. They are universal computers and, therefore, they are computationally equivalent. "[I]f one looks at a sequence of systems with progressively more complicated rules, one should expect that the overall behavior they produce will become more complex only until the threshold of universality is reached. [After that,] there should be no further fundamental change..."
One implication of his Principle of Computational Equivalence, which Wolfram draws explicitly, is that no system of any kind can ever carry out a computation that is more sophisticated than what can be carried out on a Turing machine or with a cellular automaton. That includes human brains and quantum computers.
On the other hand, the Principle of Computational Equivalence implies that any computation that can be performed by the most powerful computer can, in principle, be performed by any process that passes its low threshold of complexity. A cloud can compute a Quicksort — in principle. Another implication of the Principle of Computational Equivalence is that many of the unsolved problems of science and mathematics may remain unsolved — because they are computationally irreducible. Many of the cellular automata that Wolfram explores in loving detail in the book produce output that seems to be unpredictable by any means other than running the program and seeing what it does. Given the initial conditions and the rule governing the process, it is still impossible to short-cut the process to determine, say, the color of cell c at time t.
In traditional science and mathematics, the length of the derivation is, at most, an aesthetic issue. But Wolfram's computational approach makes explicit the fact that there is always a race between the system used to predict behavior and the system whose behavior is being predicted. The tacit assumption of science has always been that our models, through their sophistication, can outperform the process we are trying to model. The Principle of Computational Equivalence says that, unless we are willing to model limited aspects of the target system, this is not the case — our models cannot be more sophisticated than the processes they are modeling. Not if they are computations of equivalent sophistication.
It needs to be said that others have said many of these things. Ed Fredkin, for one.
Fredkin has been many things, including head of MIT's AI Lab. He is one of the world's experts on cellular automata, like Stephen Wolfram; is an atomist, like Stephen Wolfram; and has for many years entertained some of the same ideas that Wolfram spells out in his book. I can't go into all of them, but Mark Henschel pointed me to Fredkin's web site (http://www.digitalphilosophy.org/) where you can read many of his (very readable and interesting) papers. At that site, you will find many of the ideas discussed here, as well as many of the ideas in Wolfram's book not discussed here, such as the law of conservation of information. And you'll read this: "[Digital Philosophy] suggests that the Universe, with finite resources, is busy computing its future as fast as it can [and] that there is no way from within the DM Universe to, in general, predict exact future states sooner than the Universe will get to those states." Sound familiar?
Then there's David Deutsch.
Deutsch is the winner of the 1998 Paul Dirac prize for theoretical physics and a researcher at the Centre for Quantum Computation at Oxford University. Deutsch has come up with a Principle, too, one that he thinks is as important as the laws of thermodynamics. Here's how he puts it: "There exists an abstract universal computer whose repertoire includes any computation that any physical possible object can perform." Deutsch's Principle is clearly related to Wolfram's, and the relationship is a little more obvious when you realize that Deutsch's principle is merely a translation into the realm of physical objects of the familiar Church-Turing thesis: "Every function which would naturally be regarded as computable can be computed by the universal Turing machine." [Alan Turing] I leave it to you to decide how original Wolfram's Principle is.
One aspect of A New Kind of Science that I do find revolutionary is this idea of attacking head-on the question of how today makes tomorrow. Wolfram's little cellular automata chug along, generating a new generation of black and white cells at each time increment, and, for the most interesting ones, there is (Wolfram tells us) no shortcut to finding out the color of cell c at time t. The only way to find out is to run the program up to time t. Most of science as we know it, I take Wolfram to be saying, is about finding shortcuts. And most of the time, he says, there are none. You have to run the program.
Wolfram says that science as we have known it is successful because it is designed to ask only the kinds of questions that are easy for its methods to solve. When you ask, what is the relationship between this variable and that, you are not asking how some process actually works. You are asking if there is a shortcut to finding certain values. And in simple processes that unfold in symmetric or nested ways, there typically are shortcuts. So science investigates such simple processes and ignores the processes that generate most of the complexity in the universe. But true knowledge of the universe consists of understanding exactly how it works, and that means finding the program. Laws don't explain what the universe is doing; they just point out some interesting consequences of what it's doing. What it's doing is what it's doing — the program that it's executing. And in most cases, we don't know that. In most cases, Wolfram suggests, we never will. I find this viewpoint both inspiring and humbling.
Inspiring because it attempts to remove the magical action at a distance inherent in science as it is done today. Most scientific theories state a causal connection between two phenomena without specifying the steps that mediate that connection. Wolfram advocates a science that finds the actual program that nature is executing.
Humbling because he thinks that, in many cases, this will be impossible, because the program that nature is executing is like one of his cellular automata whose state at time t can only be discovered by running the program until time t. Having identified a vast realm of ignorance, Wolfram is saying that much of this realm lies forever outside the light cone of human knowledge.
Universality is the threshold of seriousness in computer design: If it's not universal, it's just a glorified calculator. Wolfram has shown that the threshold is a lot easier to reach than von Neumann and other computer pioneers thought, but it's not quite trivial.
Early designs for quantum computers didn't rise to the threshold. It was a real breakthrough when Paul Benioff designed the first quantum computer in 1981, but Benioff's model was highly abstract and idealized. Richard Feynman's 1984 quantum computer design was worse than the first digital computers that had to be rewired for every computation. As Julian Brown points out in Minds, Machines, and the Multiverse: The Quest for the Quantum Computer (Simon & Schuster, 2000; ISBN 0684814811), you would have had to effectively reinvent Feynman's computer for every new problem.
Then, in 1985, David Deutsch (him again!) published the paper "Quantum Theory, the Church-Turing Principle and the Universal Quantum Computer." While Deutsch's plan for a universal quantum computer would not have been practical to build, it did advance the field in several ways. Feynman had pushed for quantum computers because he thought that classical computers could not adequately model quantum physics — and Deutsch's quantum computer satisfied Feynman's wish: It could act as a quantum simulator. Beyond that, it was a universal computer and could do anything that any computer could do. Deutsch achieved this in a familiar way: He made the machine model an abstract Turing machine, as Benioff had done earlier, more obscurely. Beyond this, Deutsch's quantum computer could take advantage of quantum parallelism. This meant, according to the thinking of quantum computer designers, that it would be able to do things that classical computers could not do.
It is worth noting that Stephen Wolfram expresses strong doubts that this ever will prove to be the case.
Nevertheless, Deutsch had demonstrated that a universal quantum computer was a real possibility. The challenge then became to come up with a practical design and build one. To be continued.
Tom Hanlin at PowerBasic wrote to call my attention to PowerBasic. A visit to the PowerBasic site (http://www.powerbasic .com/) and some further research told me what happened to Borland's Turbo Basic. Turbo Basic was a follow-on product to Borland's hugely popular Turbo Pascal and a response to Microsoft's QuickBasic — which was a precursor to Visual Basic. Borland didn't commit to Turbo Basic for long, though. After introducing the product in 1985 or '86, within four years, Borland had sold all rights to developer Bob Gale and he had already started a company and published the first version of the successor product, PowerBasic.
By 1993, PowerBasic 3.0 was capable of compiling to 386 opcodes and featured an inline assembler. PC Magazine gave it high honors. As recently as three years ago, PowerBasic was judged the fastest DOS-based Basic around. And to answer the obvious question, quite a few. Even today, there are still quite a few DOS-based Basics around. PowerBasic is one of them, but it also comes in Windows versions. A complete standalone .EXE Hello World program written in PowerBasic reportedly compiles to just 6144 bytes on disk, or 3208 bytes in memory. That's the Windows version. The DOS version doesn't appear to have been updated in years, but it's still for sale. Remember TSRs? PowerBasic lets you create one with just five lines of code. If you don't remember TSRs, they were small programs and the initials stood for terminate-and-stay ready — and beyond that my memory is a little hazy.
DDJ