God not only plays dice in physics but also in
pure mathematics. Mathematical truth is sometimes nothing more than a perfect
coin toss
G. J.
Chaitin
The notion of randomness obsesses physicists today.
To what extent can we predict the future? Does it depend on our own
limitations? Or is it in principle impossible to predict the future? The
question of predictability has a long history in physics. In the early 19th
century
the classic deterministic laws of Isaac Newton led Pierre Simon
de Laplace to assert that the future of the Universe could be determined
forever.
Then quantum mechanics
came along. This is the theory that is fundamental to our understanding of the
nature of matter. It describes very small objects, such as electrons and other
fundamental particles. One of the controversial features of quantum mechanics
was that it introduced probability and randomness at a fundamental level to
physics. This greatly upset the great physicist Albert
Einstein, who said that “God did
not play dice”.
Then surprisingly, the
modern study of nonlinear dynamics showed
us that even the classical physics of Newton had randomness and
unpredictability at its core. The theory of chaos, as the series of articles in
New Scientist last year described, has revealed how the notion of randomness
and unpredictability is beginning to look like a unifying principle.
It seems that the same
principle even extends to mathematics. I can show that there are theorems
connected with number theory that cannot be proved because when we ask the
appropriate questions, we obtain results that are equivalent to the random toss
of a coin.
My results would have
shocked many 19th-century mathematicians, who believed that mathematical truths
could always be proved. For example, in 1900, the mathematician,
David Hilbert,
gave a famous lecture in which he proposed a list of 23 problems as a challenge
to the new century. His sixth problem had to do with establishing the
fundamental universal truths, or axioms, of physics. One of the points in this
question concerned probability theory. To Hilbert, probability was simply a
practical tool that came from physics; it helped to describe the real world
when there was only a limited amount of information available.
Another question he
discussed was his tenth problem, which was connected with solving so-called
'diophantine' equations, named after the Greek mathematician Diophantus.
These are algebraic equations involving only whole numbers, or integers.
Hilbert asked: 'Is there a way of deciding whether or not an algebraic equation
has a solution in whole numbers?'
Little did Hilbert
imagine that these two questions are subtly related. This was because Hilbert
had assumed something that was so basic to his thinking that he did not even
formulate it as a question in his talk. That was the idea that every
mathematical problem has a solution. We may not be bright enough or we may not
have worked long enough on the problem but, in principle, it should be possible
to solve it - or so Hilbert thought. For him, it was a black or white
situation.
It seems now that
Hilbert was on shaky ground. In fact, there is a connection between Hilbert's
sixth question dealing with probability theory and his tenth problem of solving
algebraic equations in whole numbers that leads to a surprising and rather
chilling result. That is: randomness lurks at the heart of that most
traditional branch of pure mathematics, number theory.
Clear, simple
mathematical questions do not always have clear answers. In elementary number
theory, questions involving diophantine equations can give answers that are
completely random and look grey, rather than black or white. The answer is
random because the only way to prove it is to postulate each answer as an
additional independent axiom. Einstein would be horrified to discover that not
only does God play dice in quantum and classical physics but also in pure
mathematics.
Where does this
surprising conclusion come from? We have to go back to Hilbert. He said that
when you set up a formal system of axioms there should be a mechanical
procedure to decide whether a mathematical proof is correct or not, and the
axioms should be consistent and complete. If the system of axioms is
consistent, it means that you cannot prove both a result and its contrary. If
the system is complete, then you can also prove any assertion to be true or
false. It follows that a mechanical procedure would ensure that all
mathematical assertions can be decided mechanically.
There is a colourful way to explain how this mechanical procedure works: the
so-called 'British Museum algorithm'. What you do - it cannot be done in
practice because it would take forever - is to use the axiom system, set in the
formal language of mathematics, to run through all possible proofs, in order of
their size and lexicographic order. You check which proofs are correct - which
ones follow the rules and are accepted as valid. In principle, if the set of
axioms is consistent and complete, you can decide whether any theorem is true
or false. Such a procedure means that a mathematician no longer needs ingenuity
or inspiration to prove theorems. Mathematics becomes mechanical.
Why mathematics is not
complete
Of course, mathematics is not like that. Kurt Goedel, the Austrian logician, and Alan
Turing, the father of the computer, showed that it is
impossible to obtain both a consistent and complete axiomatic theory of
mathematics and a mechanical procedure for deciding whether an arbitrary
mathematical assertion is true or false, or is provable or not.
Godel was the first to
devise the ingenious proof, couched in number theory, of what is called the incompleteness theorem (see 'The incompleteness
of arithmetic', New Scientist, 5 November 1987). But I think that the Turing
version of the theorem is more fundamental and easier to understand. Turing
used the language of the computer - the instructions, or program, that a
computer needs to work out problems. He showed that there is no mechanical
procedure for deciding whether an arbitrary program will ever finish its
computation and halt.
To show that the
so-called halting problem can never be solved, we set the program running on a Turing machine, which is a mathematical
idealisation of a digital computer with no time limit. (The program must be
self-contained with all its data wrapped up inside the program.) Then we simply
ask: 'Will the program go on forever, or at some point will it say 'I'm
finished' and halt ?'
Turing showed that
there is no set of instructions that you can give the computer, no algorithm,
that will decide if a program will ever halt. Godel's incompleteness theorem
follows immediately because if there is no mechanical procedure for deciding
the halting problem, then there is no complete set of underlying axioms either.
If there were, they would provide a mechanical procedure for running through
all possible proofs to show whether programs halt - although it would take a
long time, of course.
To obtain my result
about randomness in mathematics, I simply take Turing's result and just change
the wording. What I get is a sort of a mathematical pun. Although the halting
problem is unsolvable, we can look at the probability of whether a randomly
chosen program will halt. We start with a thought experiment using a general
purpose computer that, given enough time, can do the work of any computer - the
universal Turing machine.
Instead of asking
whether or not a specific program halts, we look at the ensemble of all
possible computer programs. We assign to each computer program a probability
that it will be chosen. Each bit of information in the random program is chosen
by tossing a coin, an independent toss for each bit, so that a program
containing so many bits of information, say, N bits, will have a probability of
2-N. We can now ask what is the total probability that those programs will
halt. This halting probability, call it V, wraps up Turing's question of
whether a program halts into one number between 0 and 1. If the program never
halts, V is 0; if it always halts, V is 1.
In the same way that
computers express numbers in binary notation, we can describe V in terms of a
string of 1s and 0s. Can we determine whether the Nth bit in the string is a 0
or a 1? In other words, can we compute V? Not at all. In fact, I can show that
the sequence of 0s and 1s is random using what is called algorithmic information
theory. This theory ascribes a degree of order in a set of information or data
according to whether there is an algorithm that will compress the data into a
briefer form.
For example, a regular
string of 1s and 0s describing some data such as 0101010101, which continues
for 1000 digits can be encapsulated in a shorter instruction 'repeat 01 500
times'. A completely random string of digits cannot be reduced to a shorter
program at all. It is said to be algorithmically incompressible.
My analysis shows that
the halting probability is algorithmically random. It cannot be compressed into
a shorter program. To get N bits of the number out of a computer, you need to
put in a program at least N bits long. Each of the N bits of V is an
irreducible independent mathematical fact, as random as tossing a coin. For
example, there are as many 0s in V as 1s. And knowing all the even bits does
not help us to know any of the odd bits.
My result that the
halting probability is random corresponds to Turing's assertion that the
halting problem is undecidable. It has turned out to provide a good way to give
an example of randomness in number theory, the bedrock of mathematics. The key
was a dramatic development about five years ago. James Jones of the University
of Calgary in Canada and Yuri Matijasevic of the Steklov Institute of
Mathematics in Leningrad discovered a theorem proved by Edouard Lucas in France
a century ago. The theorem provides a particularly natural way to translate a
universal Turing machine into a universal diophantine equation that is
equivalent to a general purpose computer.
I thought it would be
fun to write it down. So with the help of a large computer I wrote down a
universal-Turing-machine equation. It had 17 000 variables and went on for 200
pages. The equation is of a type that is referred to as 'exponential
diophantine'. All the variables and constants in it are non-negative integers,
0, 1, 2, 3, 4, 5, and so on. It is called 'exponential' because it contains
numbers raised to an integer power. In normal diophantine equations the power
has to be a constant. In this equation, the power can be a variable. So in
addition to having X3, it also contains XY.
To convert the
assertion that the halting probability V is random into an assertion about the
randomness of solutions in arithmetic, I need only to make a few minor changes
in this 200-page universal-Turing-machine diophantine equation. The result, my equation
exhibiting randomness, is also 200 pages long. The equation has a single
parameter, the variable N. For any particular value of this parameter, I ask
the question: 'Does my equation have a finite or infinite number of
whole-number solutions'? Answering this question turns out to be equivalent to
calculating the halting probability. The answer 'encodes' in arithmetical
language whether the Nth bit of V is a 0 or a 1. If the Nth bit of V is a 0,
then my equation for that particular value of N has a finite number of
solutions. If the Nth bit of the halting probability V is a 1, then this
equation for that value of the parameter N has an infinite number of solutions.
Just as the Nth bit of V is random - an independent, irreducible fact like
tossing a coin - so is deciding whether the number of solutions of my equation
is finite or infinite. We can never know.
To find out whether
the number of solutions is finite or infinite in particular cases, say, for k
values of the parameter N, we would have to postulate the k answers as k
additional independent axioms. We would have to put in k bits of information
into our system of axioms, so we would be no further forward. This is another
way of saying that the k bits of information are irreducible mathematical facts.
I have found an
extreme form of randomness, of irreducibility, in pure mathematics - in a part
of elementary number theory associated with the name of Diophantus and which
goes back 2000 years to classical Greek mathematics. Hilbert believed that
mathematical truth was black or white, that something was either true or false.
I think that my work makes things look grey, and that mathematicians are
joining the company of their theoretical physics colleagues. I do not think
that this is necessarily bad. We have seen that in classical and quantum
physics, randomness and unpredictability are fundamental. I believe that these
concepts are also found at the very heart of pure mathematics.