This lecture was given at a Solvay physics conference on complexity in Brussels in 1989, one of the historic series of meetings that originally involved such great names as Madame Curie, Rutherford and Poincaré. This was in fact my second Solvay conference on complexity, both of them extremely stimulating, both organized by Ilya Prigogine. At them I had the pleasure of speaking in the same place where the historic Solvay conferences were held, and of meeting the then King and Queen of Belgium and also Mr. Honda, the founder of the Japanese auto company, who provided funding for the meetings.
This idea has of course a long history in physics. In Newtonian physics there was Laplacian determinism. Then came quantum mechanics. One of the controversial features of quantum mechanics was that probability and randomness were introduced at a fundamental level to physics. This greatly upset Einstein. And then surprisingly enough with the modern study of nonlinear dynamics we realize that classical physics after all really did have randomness and unpredictability at its very core. So the notion of randomness and unpredictability begins to look like a unifying principle, and I would like to suggest that this even extends to mathematics.
I would like to suggest that the situation in mathematics is related to the one in physics: If we can't prove something, if we don't see a pattern or a law, or we cannot prove a theorem, the question is, is this our fault, is it just a human limitation because we're not bright enough or we haven't worked long enough on the question to be able to settle it? Or is it possible that sometimes there simply is no mathematical structure to be discovered, no mathematical law, no mathematical theorem, and in fact no answer to a mathematical question? This is the question about randomness and unpredictability in physics, transferred to the domain of mathematics.
One of the questions, his sixth question, had to do with axiomatizing physics. And one of the points in this question was probability theory. Because to Hilbert, probability was a notion that came from physics, having to do with the real world.
Another question that he talked about was his tenth problem, having to do with solving so-called ``diophantine'' equations, that is to say, algebraic equations where you're dealing only with integers. He asked, ``Is there a way to decide whether an algebraic equation has a solution in whole numbers or not?''
Little did Hilbert imagine that these two questions have a close connection!
There was something so basic to Hilbert's thinking that he didn't formulate it as a question in his 1900 talk. That was the idea that every mathematical problem has a solution, that if you ask a clear question you will get a clear answer. Maybe we're not smart enough to do it or haven't worked long enough on the problem, but Hilbert believed that in principle it was possible to settle every mathematical question, that it's a black or white situation. Later he formulated this as a problem to be studied, but in 1900 it was a principle that he emphasized and did not question.
What I would like to explain in this lecture is that randomness does occur in pure mathematics, it occurs in number theory, it occurs in arithmetic. And the way that it occurs ties together these three issues that Hilbert considered, because you can find randomness in connection with the problem of solving algebraic equations in whole numbers. That's Hilbert's tenth problem about diophantine equations.
Then looking at Hilbert's sixth question where he refers to probability theory, one sees that probability is not just a field of applied mathematics. It certainly is a field of applied mathematics, but that's not the only context in which probability occurs. It's perhaps more surprising that one finds probability and randomness even in pure mathematics, in number theory, the theory of whole numbers, which is one of the oldest branches of pure mathematics going back to the ancient Greeks. That's the point I'm going to be making.
This touches also on the basic assumption of Hilbert's talk of the year 1900 because it turns out that it isn't always the case that clear simple mathematical questions have clear answers.
In fact, I'll talk about some conceptually simple questions that arise in elementary arithmetic, in elementary number theory, involving diophantine equations, where the answer is completely random and looks gray rather than black or white. The answer is random not just because I can't solve it today or tomorrow or in a thousand years, but because it doesn't matter what methods of reasoning you use, the answer will always look random.
So a fancy way to summarize what I'll be talking about, going back to Einstein's displeasure with quantum mechanics, is to say, ``Not only does God play dice in quantum mechanics and in nonlinear dynamics, which is to say in quantum and in classical physics, but even in arithmetic, even in pure mathematics!''
A first point that I'd like to make, which is surprising but is very easy to understand, has to do with the notion of axiomatic reasoning, of formal mathematical reasoning based on axioms, which was studied by many people including Hilbert. In particular Hilbert demanded that when one sets up a formal axiom system there should be a mechanical procedure for deciding if a proof is correct or not. That's a requirement of clarity really, and of objectivity.
Here is a simple surprising fact: If one sets up a system of axioms and it's consistent, which means that you can't prove a result and its contrary, and also it's complete, which means that for any assertion you can either prove that it's true or that it's false, then it follows immediately that the so-called ``decision problem'' is solvable. In other words, the whole subject becomes trivial because there is a mechanical procedure that in principle would enable you to settle any question that can be formulated in the theory. There's a colorful way to explain this, the so-called ``British Museum algorithm.''
What one does---it can't be done in practice---it would take forever---but in principle one could run through all possible proofs in the formal language, in the formal axiom system, in order of their size, in lexicographic order. That is, you simply look through all possible proofs. And check which ones are correct, which ones follow the rules, which ones are accepted as valid. That way in principle one can find all theorems. One will find everything that can be proven from this set of axioms. And if it's consistent and complete, well then any question that one wants to settle, eventually one will either find a proof or else one will find a proof of the contrary and know that it's false.
This gives a mechanical procedure for deciding whether any assertion is correct or not, can be proven or not. Which means that in a sense one no longer needs ingenuity or inspiration and in principle the subject becomes mechanical.
I'm sure you all know that in fact mathematics isn't trivial. We know due to the absolutely fundamental work of Gödel and Turing that this cannot be done: One cannot get a consistent and complete axiomatic theory of mathematics, and one cannot get a mechanical procedure for deciding if an arbitrary mathematical assertion is true or false, is provable or not.
Here it's important that the program have all its data inside, that it be self contained. One sets the program running on a mathematical idealization of a digital computer. There is no time limit, so this is a very ideal mathematical question. One simply asks, ``Will the program go on forever, or at some point will it say `I'm finished' and halt?''
What Turing showed is that there is no mechanical procedure for doing this, there is no algorithm or computer program that will decide this. Gödel's incompleteness theorem follows immediately. Because if there is no mechanical procedure for deciding if a program will ever halt, then there also cannot be a set of axioms to deduce whether a program will halt or not. If one had it, then that would give one a mechanical procedure by running through all possible proofs. In principle that would work, although it would all be incredibly slow.
I don't want to give too many details, but let me outline one way to
prove that the halting problem is unsolvable, by means of a
reductio ad absurdum.
Let's assume that there is a mechanical procedure for deciding if a
program will ever halt. If there is, one can construct a program
which contains the number N, and that program will look at all
programs up to N bits in size, and check for each one whether
it halts. It then simulates running the ones that halt, all programs
up to N bits in size, and looks at the output. Let's assume
the output is natural numbers. Then what you do is you maximize over
all of this, that is, you take the biggest output produced by any
program that halts that has up to N bits in size, and let's
double the result. I'm talking about a program that given N
does this.
However the program that I've just described really is only about log
N bits long, because to know N you only need
log2 N bits in binary, right? This program is
log2 N bits long, but it's producing a result which
is two times greater than any output produced by a program up to
N bits in size. It is in fact only log N bits in size
which is much smaller than N. So this program is producing an
output which is at least twice as big as its own output, which is
impossible.
Therefore the halting problem is unsolvable. This is an
information-theoretic way of proving the unsolvability of the halting
problem.
What is the halting probability? How do I transform Turing's problem,
the halting problem, in order to get my stronger result, that not only
you have undecidability in pure mathematics but in fact you even have
complete randomness?
Well the halting probability is just this idea: Instead of asking for
a specific program whether or not it halts in principle given an
arbitrary amount of time, one looks at the ensemble of all possible
computer programs. One does this thought experiment using a
general-purpose computer, which in mathematical terms is a universal
Turing machine. And you have to have a probability associated with
each computer program in order to talk about what is the probability
that a computer program will halt.
One chooses each bit of the computer program by tossing a fair coin,
an independent toss for each bit, so that an N-bit program will
have probability 2−N. Once you've chosen the
probability measure this way and you choose your general-purpose
computer (which is a universal Turing machine) this will define a
specific halting probability.
[For this to work, it is important that the programs be self-delimiting,
i.e., for the computer to read the program in bit by bit and to
stop by itself before reading a blank at the end.
Thus no extension of a valid program is a valid program.]
This puts in one big bag the question of whether every program halts.
It's all combined into this one number, the halting probability. So
it takes all of Turing's problems and combines it into one real
number. I call this number Ω by the way. The halting probability
Ω is determined once you specify the general-purpose computer, but
the choice of computer doesn't really matter very much.
My number Ω is a probability, and therefore it's a real number
between 0 and 1. And one could write it in binary or any other base,
but it's particularly convenient to take it in binary. And when one
defines this halting probability Ω and writes it in binary, then
the question arises, ``What is the Nth bit of the halting
probability?''
My claim is that to Turing's assertion that the halting problem is
undecidable corresponds my result that the halting probability is
random or irreducible mathematical information. In other words, each
bit in base-two of this real number Ω is an independent
mathematical fact. To know whether that bit is 0 or 1 is an
irreducible mathematical fact which cannot be compressed or reduced
any further.
The technical way of saying this is to say that the halting
probability is algorithmically random, which means that to get
N bits of the real number in binary out of a computer program,
one needs a program at least N bits long.
[Can you figure out why this is the case?
Hint: If you knew the first N bits of Ω,
then you could solve the halting problem for all programs
up to N bits in size.]
That's a technical
way of saying this. But a simpler way to say it is this: The
assertion that the Nth bit of Ω is a 0 or a 1 for a
particular N, to know which way each of the bits goes, is an
irreducible independent mathematical fact, a random mathematical fact,
that looks like tossing a coin.
And you know Gödel had the same problem. When he originally
constructed his unprovable true assertion, it was bizarre. It said,
``I'm unprovable!'' Now that is not the kind of mathematical
assertion that one normally considers as a working mathematician.
Gödel devoted a lot of ingenuity, some very clever, brilliant and
dense mathematics, to making ``I'm unprovable'' into an assertion
about whole numbers. This includes the trick of Gödel numbering
and a lot of number theory.
There has been a lot of work deriving from that original work of
Gödel's. In fact that work was ultimately used to show that
Hilbert's tenth problem is unsolvable. A number of people worked on
that. I can take advantage of all that work that's been done over the
past sixty years. There is a particularly dramatic development, the
work of Jones and Matijasevic which was published about five years
ago.
They discovered that the whole subject is really easy, which is
surprising because it had been very intricate and messy. They
discovered in fact that there was a theorem proved by Édouard
Lucas a hundred years ago, a very simple theorem that does the whole
job, if one knows how to use it properly, as Jones and Matijasevic
showed how to do.
So one needs very little number theory to convert the assertion about
Ω that I talked about into an assertion about whole numbers, an
arithmetical assertion. Let me just state this result of Lucas
because it's delightful, and it's surprisingly powerful. That was of
course the achievement of Jones and Matijasevic, to realize this.
The hundred-year old theorem of Lucas has to do with when is a
binomial coefficient even and when is it odd. If one asks what is the
coefficient of XK in the expansion of
(1+X)N, in other words, what is the
Kth binomial coefficient of order N, well the answer is
that it's odd if and only if K implies N---on a bit by
bit basis, considered as bit strings. In other words, to know if a
binomial coefficient ``N choose K'' is odd, what you
have to do is look at each bit in the lower number K that's on,
and check if the corresponding bit in the upper number N is
also on. If that's always the case on a bit by bit basis, then, and
only then, will the binomial coefficient be odd. Otherwise it'll be
even.
This is a remarkable fact, and it turns out to be all the number
theory one really needs to know, amazingly enough.
Well, the result of this is a diophantine equation. I thought it
would be fun to actually write it down, since my assertion that there
is randomness in pure mathematics would have more force if I can
exhibit it as concretely as possible. So I spent some time and effort
on a large computer and with the help of the computer I wrote down a
two-hundred page equation with seventeen-thousand variables.
This is what is called an exponential diophantine equation. That is
to say, it involves only whole numbers, in fact, non-negative whole
numbers, 0, 1, 2, 3, 4, 5, ... the natural numbers. All the variables
and constants are non-negative integers. It's called ``exponential
diophantine,'' ``exponential'' because in addition to addition and
multiplication one allows also exponentiation, an integer raised to an
integer power. That's why it's called an exponential diophantine
equation. That's also allowed in normal polynomial diophantine
equations but the power has to be a constant. Here the power can be a
variable. So in addition to seeing X3 one can also
see XY in this equation.
So it's a single equation with 17,000 variables and everything is
considered to be non-negative integers, unsigned whole numbers. And
this equation of mine has a single parameter, the variable N.
For any particular value of this parameter, I ask the question, ``Does
this equation have a finite number of whole-number solutions or does
this equation have an infinite number of solutions?''
The answer to this question is my random arithmetical fact---it turns
out to correspond to tossing a coin. It ``encodes'' arithmetically
whether the Nth bit of Ω is a 0 or a 1. If the Nth
bit of Ω is a 0, then this equation, for that particular value of
N, has finitely many solutions. If the Nth bit of the
halting probability Ω is a 1, then this equation for that value of
the parameter N has an infinite number of solutions.
The change from Hilbert is twofold: Hilbert looked at polynomial
diophantine equations. One was never allowed to raise X to the
Yth power, only X to the 5th power. Second, Hilbert asked ``Is
there a solution? Does a solution exist or not?'' This is
undecidable, but it is not completely random, it only gives a certain
amount of randomness. To get complete randomness, like an independent
fair coin toss, one needs to ask, ``Is there an infinite number of
solutions or a finite number of solutions?''
Let me point out, by the way, that if there are no solutions, that's a
finite number of solutions, right? So it's one way or the other. It
either has to be an infinite number or a finite number of solutions.
The problem is to know which. And my assertion is that we can never
know!
In other words, to decide whether the number of solutions is finite or
infinite (the number of solutions in whole numbers, in non-negative
integers) in each particular case, is in fact an irreducible
arithmetical mathematical fact.
So let me emphasize what I mean when I say ``irreducible mathematical
facts.'' What I mean, is that it's just like independent coin tosses,
like a fair coin. What I mean, is that essentially the only way to
get out as theorems whether the number of solutions is finite or
infinite in particular cases, is to assume this as axioms.
In other words, if we want to be able to settle K cases of this
question---whether the number of solutions is finite or not for
K particular values of the parameter N---that would
require that K bits of information be put into the axioms that
we use in our formal axiom system. That's a very strong sense of
saying that these are irreducible mathematical facts.
I think it's fair to say that whether the number of solutions is
finite or infinite can therefore be considered to be a random
mathematical or arithmetical fact.
To recapitulate, Hilbert's tenth problem asks ``Is there a solution?''
and doesn't allow exponentiation. I ask ``Is the number of solutions
finite?'' and I do allow exponentiation.
In the sixth question, it is proposed to axiomatize probability theory
as part of physics, as part of Hilbert's program to axiomatize
physics. But 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 Diophantos and which goes back two
thousand years to classical Greek mathematics.
Moreover, my work is an extension of the work of Gödel and Turing
which refuted Hilbert's basic assumption in his 1900 lecture, that
every mathematical question has an answer---that if you ask a clear
question there is a clear answer. Hilbert believed that mathematical
truth is black or white, that something is either true or false. It
now looks like it's gray, even when you're just thinking about the
unsigned whole numbers, the bedrock of mathematics.
Modern mathematical self-examination really starts I believe it is
fair to say with Cantor's theory of the infinite and the paradoxes and
surprises that it engendered, and with the efforts of people like
Peano and Russell and Whitehead to give a firm foundation for
mathematics.
Much hope was placed on set theory, which seemed very wonderful and
promising, but it was a pyrrhic victory---set theory does not help!
Originally the effort was made to define the whole numbers 1, 2, 3,
... in terms of sets, in order to make the whole numbers clearer and
more definite.
However, it turns out that the notion of set is full of all kinds of
paradoxes. For example the notion of the universal set turns out to
be inadmissible. And there are problems having to do with large
infinities in set theory. Set theory is fascinating and a vital part
of mathematics, but I think it is fair to say that there was a retreat
away from set theory and back to 1, 2, 3, 4, 5, ... Please don't touch
them!
I think that the work I've described, and in particular my own work on
randomness, has not spared the whole numbers. I always believed, I
think most mathematicians probably do, in a kind of Platonic universe.
``Does a diophantine equation have an infinite number of solutions or
a finite number?'' This question has very little concrete
computational meaning, but I certainly used to believe in my heart,
that even if we will never find out, God knew, and either there were a
finite number of solutions or an infinite number of solutions. It was
black or white in the Platonic universe of mathematical reality. It
was one way or the other.
I think that my work makes things look gray, and that mathematicians
are joining the company of their theoretical physics colleagues. I
don't think that this is necessarily bad. We've 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.
Future Work: In this discussion the probabilities that arise
are all real numbers. Can the probability amplitudes of quantum
mechanics, which are complex numbers, be used instead?
The Halting Probability Ω
Okay, so I start with Turing's fundamental result on the unsolvability
of the halting problem, and to get my result on randomness in
mathematics, what I do is I just change the wording. It's sort of a
mathematical pun. From the unsolvability of the halting problem, I go
to the randomness of the halting probability.
Arithmetization
Now you will of course immediately say, ``This is not the kind of
mathematical assertion that I normally encounter in pure
mathematics.'' What one would like, of course, is to translate it
into number theory, the bedrock of mathematics.
Randomness in Arithmetic
So what is the result of using this technique of Jones and Matijasevic
based on this remarkable theorem of Lucas?
The Philosophy of Mathematics
This has been a century of much excitement in the philosophy and in
the foundations of mathematics. Part of it was the effort to
understand how the calculus (the notion of real number, of limit)
could be made rigorous---that goes back even more than a hundred years.
Further Reading