Dr. Dobb's Journal August, 2004
In some versions of this idea, the program/computer is a cellular automaton. This doesn't seem to be a reduction in generality of the idea, but more a notational convenience. Cellular automata are, or can be, universal computers, equivalent to a universal Turing machine. A cellular automaton for the universe would consist of a massive transformation rule that specified how the cells of a digital grid of elemental events changes during one tick of the universal clock. This metarule would generate the next instant in the history of the universe from the previous one by means of rules like those in the Game of Life, where a cell with two or three occupied neighboring cells becomes occupied on the next step, and a cell becomes unoccupied if its neighborhood is less or more dense than this.
The universe, under this idea, is strictly digital. There is no physical realization of the mathematical notion of a real number: Only integers describe real things because everything—matter, energy, space, time, consciousness—is ultimately discrete. This idea, as one exponent (Ed Fredkin) puts it, "is an atomic theory carried to a logical extreme where all quantities in nature are finite and discrete. This means that, theoretically, any quantity can be represented exactly by an integer."
Uh-huh. The universe is a computer program, and a digital one at that. Wow, what a radical thing for someone whose academic background is in computer science to say to an audience of programmers.
Okay, but some very smart people think there may be something to this idea of the universe as a computation. I've probed the views of some exponents of this view here in this column: Stephen Wolfram with his New Kind of Science and Edward Fredkin with his Digital Philosophy. Now add to these Gregory J. Chaitin, inventor of Algorithmic Information Theory.
All three theories, as articulated in their books:
pull together mathematics, theoretical physics, and computer science in a new synthesis. But these are not quite mainstream views: For one thing, modern theoretical physics is done using ordinary and partial differential equations, not integer arithmetic. It would seem either that most modern physicists have got it wrong or that the Digital Philosophers have. I don't know which is the case, but I know that you get into more interesting questions if you bet on the outsiders. Like Wolfram, Fredkin, and Chaitin.
Gregory Chaitin works at the IBM Watson Research Center in New York. As a teenager, he tried to interest the legendary Kurt Göodel in his theories. Göodel was too busy, but the teenager's ideas were very clever and have proved extremely fruitful. For four decades, Chaitin has been the driving force behind what he calls "Algorithmic Information Theory." He also came up with one of the most interesting numbers there is—Chaitin's Omega.
But to get to that interesting number, it is first necessary to talk about uninteresting numbers.
The concept of an uninteresting number comes up in Berry's Paradox, which was, paradoxically, not invented by Berry, although G.G. Berry, an Oxford librarian, did suggest the idea to Bertrand Russell, who turned it into a serious topic for mathematical and philosophical inquiry and named it after his librarian friend.
Berry's Paradox is exemplified by the phrase, "The first natural number that cannot be named in fewer than fourteen words." That phrase contains 13 and purports to name a number that can't be named in fewer than 14 words, hence, the paradox.
You can also ask what is the smallest uninteresting number, and whatever the answer, it will be paradoxical, because the smallest uninteresting number is interesting by virtue of being the smallest uninteresting number. There are various ways to make the concept of uninterestingness concrete enough to make the paradox interesting and the Berry Paradox is one.
Chaitin did to the Berry Paradox what Göodel had famously done to the Liar Paradox in developing his results on the inherent incompleteness of arithmetic and other formal systems.
The Liar Paradox involves the statement, "This statement is false." If it really is false, then what it says is true, and if it's true, then it's false. Paradox.
Göodel varied the statement to read, "This statement is unprovable [in a particular formal axiomatic theory, such as arithmetic with addition and multiplication]." He showed that, to avoid the analog of the Liar Paradox, one had to conclude that arithmetic and all sufficiently complex formal axiomatic systems are incomplete: That there are true statements in them that cannot be proved in the systems.
Chaitin did the same trick with the paradoxical phrase in the Berry Paradox. He transformed it to "The first natural number that can be proved [in a particular formal axiomatic theory] to have the property that it cannot be specified [on a particular universal Turing machine] by a computer program with fewer than N bits."
That looks considerably different, but it's the same kind of transformation that Göodel did on the Liar Paradox statement, and Chaitin gets analogous results. He shows that there is, in fact, a computer program of fewer than N bits that computes the number that this statement says can't be computed in fewer than N bits, and like Göodel, he uses the contradiction to prove an incompleteness result.
This incompleteness result has many consequences, including the fact that you can never prove that there is no program shorter than a given program that produces the same output.
Say you feed random bits to a Turing machine. That is, you flip a coin or perform some other sequence of actions that produces a truly random sequence of 1s and 0s, and you feed these 1s and 0s to a Turing machine as its data. What is the probability that the Turing machine will eventually halt? The question has, for any given Turing machine, a precise answer, a particular real number between 0 and 1. That number is Chaitin's Omega. This is one way of defining Chaitin's Omega.
Chaitin's Omega is not a single number, but rather depends on the specification of the Turing machine in the definition above. But for any given Turing machine, Chaitin's number is a specific positive real number. And it turns out to be a very interesting one.
Philosophers, mathematical cranks, and mystics have long sought some wonderful number that would encompass all knowledge. Philosopher Charles Sanders Peirce was obsessed with the number 3. Chaitin's Omega has more digits than Peirce's, and it also really does encode a remarkable amount of very precious information. It contains the answers to most of the open questions in mathematics.
It has some other interesting properties. It is maximally dense, in a sense that seems (but only seems) to defy the Berry Paradox. And it is random in the strongest possible sense. Chaitin was one of those who came up with that strongest definition of randomness—that something is random only if no shorter description for it exists. Omega is random in that sense.
Chaitin's Omega compactly encodes all solutions to the halting problem. If the first few thousand digits of Omega were known, we would be able to solve most of the open problems in mathematics and theoretical computer science.
This would be done (in theory!) by decomposing a sum of probabilities. Since Omega is defined to be the halting probability of a Turing machine with random input, it is really the sum of the halting probabilities of all possible programs. So what you do is, you start feeding programs to the Turing machine on a "Twelve Days of Christmas" schedule: Run the first program one step, then run the second program one step and the first one a second step, then the third program one step and the second a second step and the first a third step...And so on, and you do a little math on the output.
Sounds good to me. I'm ready to start now, but apparently there are practical difficulties.
Chaitin's philosophy of digitalness seems congruent to Wolfram's and Fredkin's. One area where it leads him is to the notion of the essentially empirical nature of mathematics.
Wolfram effectively credits Chaitin and Kurt Göodel with the philosophical justification for Wolfram's entire New Kind of Science research program. He says:
The idea that as a matter of principle there should be truths in mathematics that can only be reached by some form of inductive reasoning—like in the natural sciences—was discussed by Kurt Göodel in the 1940s and Gregory Chaitin in the 1970s. But it received little attention.
Chaitin says that mathematics can be, indeed must sometimes be, an experimental discipline. As in natural science, there are as a matter or principle some mathematical truths that you cannot arrive at through deductive reasoning within an axiomatic system.
Here's how he arrives at that:
In Chaitin's incompleteness results, he doesn't exactly conclude that you absolutely can't, for example, prove that a particular program is the shortest possible program that produces its particular output. It's just that, to prove it, you would need more bits worth of axioms in the system than there are in the result. You'd be putting as much in as you're getting out. You might as well stipulate the result as an axiom, because you'll never prove it within the system otherwise, even though you might have excellent reasons, outside this particular formal axiomatic system, to believe it to be true.
Chaitin claims that mathematics is full of results that are just true for no good reason, and that the only way to get them into your theories is to add them as axioms. When you come across one, it is a discovery, like the empirical discoveries in other sciences. Mathematics is an empirical science.
This ties in nicely with the universe-as-computation idea. The universe is cranking out tomorrows as fast as it can, and there is no algorithm that can do it faster. So the future is not just unknowable in practical terms, it is inherently unknowable. We'll know it when it happens, and not before.
DDJ