Dr. Dobb's Journal August 2002
"I do not know what I may appear to the world; but to myself I seem to have been only like a boy playing on the sea-shore, and diverting myself in now and then finding a smoother pebble or a prettier shell than ordinary, whilst the great ocean of truth lay all undiscovered before me."
— Isaac Newton
This month, I'm writing about Stephen Wolfram's magnum opus, A New Kind of Science (Wolfram Media, 2002; ISBN 1-57955-008-8). This 1200-page, half-a-million-word book is the most astonishing thing I've read in a long time. One of the astonishing things about the book is its ambition. Like Newton, Wolfram sees the achievements of science as instances of playing in puddles on the shore while the great ocean of truth lies undiscovered near at hand. Unlike Newton, Wolfram wades in.
"[T]he entire fabric of human reason which we employ in the inquisition of nature is badly put together and built up, and like some magnificent structure without any foundation," Francis Bacon wrote in his magnum opus, The New Organon, published in 1620. "There was but one course left, therefore — to try the whole thing anew upon a better plan, and to commence a total reconstruction of sciences, arts, and all human knowledge, raised upon the proper foundations."
Wolfram's ambition is no less modest — he intends a total reconstruction of science and all human knowledge, erected on the foundation he lays out in this book.
Wolfram says that science has thus far huddled on that safe shore, asking only those questions that its established methods have a good chance of answering. In doing so, it has avoided a vastly larger realm of questions — questions that Wolfram proposes tackling with the method he has been exploring for the past 20 years. That's what his book is about.
I won't attempt here to judge how well it succeeds, but I'll at least try to give a sense of what Wolfram thinks he's figured out. I also have another installment of my thread on quantum computing.
Ten years ago this fall, DDJ senior editor Ray Valdez and I sat down with Stephen Wolfram to talk about Mathematica (which he created), mathematics, and whatever might be on Wolfram's mind. The result of that conversation was published in this column in the January and February 1993 issues of DDJ. At the end of that published interview, after sharing his views on more narrow technical issues, Wolfram said:
It's actually an interesting historical thing that I've been studying, how partial differential equations ended up being thought by people to be the fundamental equations of physics. It's very bizarre, because it isn't true, and not only is it not true, even the fact that atoms exist makes it clear that it's not true. So why is it that people will [say] that the fundamental equations of physics are partial differential equations?
What happened, I think, is that when these models were first developed, the only methods for figuring out what the consequences were was hand calculation. Computers are a very recent phenomenon in the history of science, and the fundamental models that exist in science have not yet adapted to computation. And that's my next big thing.
That was his plan 10 years ago: To use basic ideas from computation to figure out the correct models of physics. "Next big thing" indeed. At the time, this looked like an outrageously ambitious plan, but I suspected that Wolfram might just be the guy to pull it off. I do think that Wolfram may be a Newton-scale intellect. I'm sure he has Newton-scale ambition.
Ten years later, the ambition of Wolfram's plan has ballooned. In 1992, he was still willing to talk about looking for the fundamental equations of physics. Now, he's apparently convinced that the whole idea of looking for simple equations is the wrong way to do science. Or put it this way: That the way of doing science pursued by every scientist since Isaac Newton amounts to picking the low-hanging fruit from the tree of knowledge. Based on what he said in that interview, in 1992 Wolfram saw computers as a tool for finding the right equations. Today, he sees computation as the method for doing direct experimental research on the fundamental processes by which the universe works. He isn't talking about simulation — his approach isn't to model the clockworks of the universe, but to find the actual program by which today makes tomorrow. Program, not equation: For equations, Wolfram would substitute simple programs as the proper form of scientific law. And along the way, he would throw out the continuum: For continuous models like partial differential equations, he would substitute discrete computations. Again, not as an approximation, not as a simulation.
He thinks the universe is discrete. He thinks it's digital. And it's no longer just physics that he's trying to rebuild from the foundation up. All of science, Wolfram believes, needs to be reconstructed along lines that he lays out in his book. Physics. Biology. Cognitive science. Economics. His approach promises answers, or a path to answers, to such puzzles as free will, intelligence, and how all this bewildering complexity could have come from simple beginnings. He thinks he's found the key to everything.
"In my early years," Wolfram says, "I was very much a part of the traditional scientific community."
Technically correct, but Wolfram was never much a part of the traditional system of educating scientists. He never had the patience to attend college classes or to finish any traditional academic degree program, although after he had spent a year at Cal Tech, the university granted him a Ph.D. The number and quality of his professional publications demanded it. At Cal Tech, and later at the Institute for Advanced Studies and the University of Illinois, there was something about Wolfram that rubbed people the wrong way. He had little patience with people whom he considered his intellectual inferiors — and that was most of the planet — and he had no tact at all.
"[H]ad I remained there," he says, "I have little doubt that I would never have been able to create something of the magnitude [of what] I describe in this book."
But he didn't have to remain there. While he was at Cal Tech, Wolfram became the youngest person ever to be awarded a MacArthur Fellowship, often called the "genius grants." The MacArthur Prize carried with it enough money to let a genius pursue his or her research interests for a good stretch of time, although probably not as long as Wolfram has been at it. For that, he has Wolfram Research, the company he built to sell the program that he wrote, Mathematica. The success of Mathematica and his ownership of this profitable, private company created an intriguing situation: One of the brightest people on the planet has had all the money he needs and precisely the tools he needs to pursue whatever research he wishes with no academic responsibilities.
Wolfram has made the most of it, devoting nearly all his time to a single area of research. He is right, too: As part of the traditional scientific community, he probably could not have retreated to an attic room for a decade obsessed with what his colleagues regard as mere recreational mathematics, and it would have been a bit of a challenge to get 10 years of funding for a plan to prove that the god program of the universe is a cellular automaton.
Some of us discovered cellular automata, or CAs, through Martin Gardner's February 1971 "Mathematical Games" column in Scientific American, where he introduced John Horton Conway's CA called the "Game of Life." I probably don't need to remind you that the Game of Life involves binary cells in a grid, each either "on" or "off" and all simultaneously updated on each play of the game according to a simple rule. Conway's rule is: Each on cell with two or three orthogonally adjacent on neighbors stays on; each off cell with exactly three on neighbors goes on; every other cell stays off or turns off. I should remind you that Conway chose this rule carefully to make the behavior of the system over time interesting and unpredictable.
(First aside: Conway's still into games, as his talk at http://technetcast.ddj.com/tnc_play_stream.html?stream_id=672 proves. Second aside: While researching something else, I stumbled across what is probably my own first implementation of the Game of Life. Since it was written under weekly deadline pressure for the October 11, 1982 issue of InfoWorld and coded in The Software Works Forth for the Osborne 1 computer, I'll spare you the code.)
Others discovered cellular automata through some of the fascinating work done on them in the field known as artificial life, popularized in Steven Levy's Artificial Life (Vintage Books, 1992; ISBN 0-679-74389-8). But the history of CAs extends back decades earlier: Edward Fredkin, former head of MIT's Project MAC, was exploring CAs in 1960, and John von Neumann and Stanislaw Ulam really pioneered the field over a decade before that. Konrad Zuse, one of the inventors of the digital computer, independently invented CAs. Tommaso Toffoli and Alvy Ray Smith have also done significant CA work.
I have to give credit to the other explorers in this territory because giving credit to others is not Wolfram's long suit. "His gracelessness toward his predecessors knows no bounds," Levy wrote in Artificial Life.
But maybe Wolfram has improved. Although the 800-plus pages in the main body of A New Kind of Science read as though no one had ever thought any of these things before Stephen Wolfram shone the light of his prodigious intellect on them, the 300-plus pages of notes go some distance toward acknowledging others' work. (And the notes, printed in smaller type, actually run 50,000 words longer than the main text.)
It is a fact that the study of cellular automata was languishing before Wolfram dismayed his IAS colleagues by dropping quantum chromodynamics to take up this seemingly frivolous subject, and that it was reinvigorated by a series of papers by Wolfram in the 1980s.
Wolfram prefers the simplicity of the one-dimensional CA. Here's a description: Picture an infinitely long line of pixels, each either black or white. That's your input to your 1D CA; the initial conditions. Wolfram often works with extremely simple initial conditions, like one black pixel and the rest white, or alternating black and white pixels. Now apply a nearest neighbor rule to all the pixels simultaneously, a rule like "if the pixels immediately to the right and left of me are black and I am white, I go black; otherwise I become or remain white." Apply the rule repeatedly. To see what is happening over time, Wolfram shows each successive generation of pixels below the previous one, so the diagrams of his 1D CAs are two-dimensional, but the second dimension is time.
Wolfram noticed something odd about some of these CAs. One in particular seemed to be able to produce infinite complexity from an extremely simple rule and trivially simple initial conditions. Others had noticed this odd feature of CAs. It was almost what Conway had in mind in picking the Game of Life rule so as to make its behavior "interesting and unpredictable." But Wolfram began to understand this as a discovery of the utmost importance. In information-theoretic terms, it looks like a violation of the second law of thermodynamics: How does all that complexity come out of such simplicity? Where does it come from? And what are the implications of being able to generate complexity out of simplicity?
That's the question on which Wolfram has spent the past 10 years of his life, the question on which he hangs the half-million words of this book, and the question that he thinks knocks the props out from under science as we know it. The answer, briefly, is CAs.
CAs are computer programs, but they are vastly simpler than the kind of programs that scientists usually use in trying to model nature or physics.
They are no less powerful, though. Edward Fredkin preceded Wolfram in seeing that certain simple CAs were complex enough to model physics, and the artificial life people see them as a way to explore the processes of life. But Wolfram has carefully detailed all the complex systems to which CAs are computationally equivalent. For starters, Turing machines. Simple CAs have the computational power of a Turing machine, which means that they are computationally equivalent to any computer. Wolfram doesn't stop with stating this theoretical result; he shows how to compute with CAs. He explores generalized CAs (continuous, mobile, totalizing), substitution systems (including fractals), production systems or string rewriting systems, register machines, recursive functions, and the tag systems developed by Emil Post for implementing syntactic reduction rules in Principia Mathematica. He shows how to emulate these kinds of systems with CAs, and how to emulate CAs with these kinds of systems.
They are all, he says, equivalent. Wolfram enshrines this equivalence in a principle he calls the "Principle of Computational Equivalence." Not only are CAs and Turing machines and such computationally equivalent, but they are all computationally equivalent to thunderstorms, airfoil turbulence, and human consciousness. So far, this sounds like the Church-Turing thesis.
I'm not sure, at least after one reading of the book, what Wolfram intends here beyond what is already well accepted, unless it is that this computational equivalence is not just a fact about math or computer science or logic, but is a fact about the physical nature of the universe.
But if that's what he means, David Deutsch said it first in 1985. Deutsch, a professor at the University of Oxford, is one of the leading lights in quantum computing, credited with first elucidating the concept of quantum parallelism.
I think I'll have to study Wolfram's Principle of Computational Equivalence further and, if I figure it out, discuss it here next month. In any case, Wolfram demonstrates that CAs can embody more general rules than can the mathematical equations that make up most of science. And this means that they can go to places where science has not gone before. Put it this way: Despite the dazzling success of science in uncovering connections among the phenomena of nature and giving us better guesses about aspects of the future, the mystery of the succession of events remains. At one instant, everything that is, is exactly the way it is; in the next instant, everything is different. What is the rule that maps one instant onto the next? Isn't this the real job of science: to explain how today makes tomorrow? That's the challenge Wolfram lays out in A New Kind of Science.
One huge gap in A New Kind of Science is its almost total ignoring of quantum physics, especially quantum computation. Deutsch thinks that this alone wrecks Wolfram's thesis. Responding to a request from the Daily Telegraph for his first impressions on A New Kind of Science, Deutsch wrote: "I was disappointed that there is only the barest mention of quantum computation. If computation-based ideas really are going to play a fundamental role in physics, it will have to be through the quantum theory of computation...not the classical one that this book is based on."
Indeed, Richard Feynman, the previous-generation boy genius whom boy genius Wolfram encountered at Cal Tech, pointed out as early as 1981 that there are quantum phenomena, like the EPR effect, that simply cannot be emulated by a classical computer — only by a quantum computer. Deutsch again: "Hence my first impression is that the book's central thesis is false: I do not think that the sciences...will be revolutionised by reinterpreting nature in terms of simple computational rules rather than simple equations."
On the other hand, maybe Wolfram's approach can handle quantum phenomena. Edward Fredkin would probably think so, since he, like Wolfram, believes that the universe is discrete, not continuous; that it is fundamentally computational, and that the ultimate program of the universe is a cellular automaton. Fredkin calls his theory "Digital Mechanics" and he is convinced that it should be able to explain quantum phenomena like the EPR effect.
DDJ