In a famous lecture in 1900, David Hilbert listed 23 difficult problems he felt deserved the attention of mathematicians in the coming century. His conviction of the solvability of every mathematical problem was a powerful incentive to future generations: ``Wir müssen wissen. Wir werden wissen.'' (We must know. We will know.) Some of these problems were solved quickly, others might never be completed, but all have influenced mathematics. Later, Hilbert highlighted the need to clarify the methods of mathematical reasoning, using a formal system of explicit assumptions, or axioms. Hilbert's vision was the culmination of 2,000 years of mathematics going back to Euclidean geometry. He stipulated that such a formal axiomatic system should be both `consistent' (free of contradictions) and `complete' (in that it represents all the truth). Hilbert also argued that any well-posed mathematical problem should be `decidable', in the sense that there exists a mechanical procedure, a computer program, for deciding whether something is true or not. Of course, the only problem with this inspiring project is that it turned out to be impossible.
In 1931 Kurt Gödel showed that if you assume a formal axiomatic system containing elementary arithmetic is consistent (which is the minimum requirement—if you can prove false results that is embarrassing), then you can prove that it is incomplete. This was a huge surprise; everyone else thought Hilbert was right. The third condition remained open until Alan Turing demolished Hilbert's dream in 1936. Turing showed that no mechanical procedure, and therefore no formal axiomatic theory, can solve Turing's halting problem, the question of whether a given computer program will eventually halt. Turing's argument was based on computable real numbers. A real number, such as π, is a length measured with arbitrary precision, with an infinite number of digits. And a real number is computable if there is a computer program or algorithm for calculating its digits one by one. There are programs for calculating π, but it is a surprising fact that nearly all real numbers are not computable. Turing showed that if you could find a mechanical procedure to decide if a computer program will ever halt, then you could compute a real number that is not actually computable, which is impossible.
In 1975 a more modern version of Turing's halting problem emerged. This is Chaitin's Ω number, which is the probability that an arbitrary computer program will eventually halt1. Ω is computable in a weak sense, but its binary digits or bits are algorithmically random and cannot be distinguished from the result of independent tosses of a fair coin. Now Theodore Slaman2 and Robert Solovay3 have greatly increased our understanding of Ω and the depth and pervasiveness of its algorithmic randomness. Their work brings up to date the theoretical context for studying Ω, called algorithmic information theory4,5, and reinforces the limits placed on the power of mathematical reasoning by this theory6.
To understand Ω better, let's compare it with another well-known real number, π. The digits of π (3.1415926...) can be computed one by one; nonetheless, if examined locally, without being aware of their provenance, they appear `random'. People have calculated π out to one billion or more digits. One of the reasons for doing this, besides breaking the world record, is the question of whether each digit occurs the same number of times. It looks likely, but remains unproven, that the digits 0 through 9 each occur 10% of the time in a decimal expansion of π. If this turns out to be true, then π would be called a simply normal real number. But although π may be random in so far as it's `normal', it is far from random in the sense of algorithmic information theory, because its infinity of digits can be compressed into a concise computer program for calculating them.
Now let's consider Ω. Although it has a simple mathematical definition, this definition does not enable us to determine more than a finite number of its digits, which can be shown to be `normal' in base ten and indeed in any base (for example, in binary, 0 and 1 will occur exactly 50% of the time). Moreover, although the infinite amount of information contained in Ω's digits is algorithmically incompressible, it turns out that Ω is `computably enumerable', which means that it can be calculated by an infinite process during which one can never know how close one is to the final value. In this way, the halting probability Ω shares two apparently irreconcilable properties: `algorithmic randomness' and `computable enumerability'.
An Ω is computably enumerable because a systematic run of all programs will produce better and better approximations (without being able to compute its digits exactly), and random because it is incompressible; there is no better way to find its digits than by tossing a fair coin. No formal mathematical theory can determine more than a finite number of digits of an Ω. In fact, one can explicitly compute a limit on the number of digits of Ω that a specific theory can determine4,5. Berkeley mathematician Robert Solovay3 has now constructed the `worst ever' Ω for which no bit can be determined even with the help of the most powerful formal axiomatic system used by mathematicians, known as Zermelo-Fraenkel set theory.
Each Ω depends on the choice of the computing machine, so there is not just one Ω (as there is only one π), but a class of Ωs. Are there random real numbers other than Ωs that are computably enumerable? This question originates in a 215-page manuscript written by Solovay in 1975 (unpublished manuscript, IBM T.J. Watson Research Center, New York). For years, people working in complexity theory felt that the answer was positive. Solovay imagined a new class of Ω-like numbers that would be distinct from Ωs and would separate them from the other computably enumerable random real numbers (Fig. 1). The intention was to make an Ω-like number share the paradoxical status of an Ω, but not all the properties of a true Ω; Ω-like numbers would then outnumber the Ωs. An Ω-like real number behaves like an oracle: its huge amount of information can be used to compute close approximations for every computably enumerable real number.
In 1998 a first unexpected result was proved: every Ω-like real number is an Ω7. The existence of a computably enumerable random real number that is not an Ω became less plausible, but was not ruled out. The last step has been brilliantly accomplished by another Berkeley mathematician, Theodore Slaman2, who has proved that every computably enumerable random real number is Ω-like, and hence an Ω.
This recent work reinforces the message of algorithmic information theory that randomness is as fundamental and as pervasive in pure mathematics as it is in theoretical physics. In our opinion it also gives further support to `experimental mathematics', and to the `quasi-empirical' view of mathematics which says that although mathematics and physics are different, it is more a matter of degree than black and white4,5,8. Physicists are used to working with assumptions that explain a lot of data, but that can be contradicted by subsequent experiments. But mathematicians don't like having to backpedal. Even after Gödel and Turing showed that Hilbert's dream didn't work, in practice most mathematicians carried on as before, in Hilbert's spirit. But now, finally, the computer is changing the way we do things. It is easy to run a mathematical experiment on a computer, but you can't always find a proof to explain the results. So in order to cope, mathematicians are sometimes forced to proceed in a more pragmatic manner, like physicists. The Ω results provide a theoretical underpinning for this revolution.
C.S. Calude is in the Department of Computer Science, Auckland University, Private Bag 92019, Auckland, New Zealand. e-mail: cristian@cs.auckland.ac.nz
G.J. Chaitin is at the IBM T.J. Watson Research Center, PO Box 704, Yorktown Heights, New York 10598, USA. e-mail: chaitin@watson.ibm.com
|
Figure 1 Complexity theorists used to believe that these three classes of real numbers were different. Work by Berkeley mathematician Theodore Slaman2 shows that these three classes of real numbers in fact collapse into a single class. This work helps to clarify the nature of randomness in pure mathematics—it is as fundamental as it is in theoretical physics.
