Lecture —
Undecidability & Randomness in Pure Mathematics

[Originally published in G. J. Chaitin, Information, Randomness & Incompleteness, 2nd Edition, World Scientific, 1990, pp. 307-313.]

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.

Abstract

I have shown that God not only plays dice in physics, but even in pure mathematics, in elementary number theory, in arithmetic! My work is a fundamental extension of the work of Gödel and Turing on undecidability in pure mathematics. I show that not only does undecidability occur, but in fact sometimes there is complete randomness, and mathematical truth becomes a perfect coin toss.

Randomness in Physics

What I'd like to talk about today is taking an important and fundamental idea from physics and applying it to mathematics. The fundamental idea that I'm referring to is the notion of randomness, which I think it is fair to say obsesses physicists. That is to say, the question of to what extent is the future predictable, to what extent is our inability to predict the future our limitation, or whether it is in principle impossible to predict the future.

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.

The Hilbert Problems

One way to orient our thinking on this question, is to recall the famous lecture given by Hilbert ninety years ago in 1900 in which he proposed a famous list of twenty-three problems as a challenge to the new century, a century which is now almost over.

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!''

Formal Axiom Systems

What is the evolution of ideas leading to this surprising conclusion?

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.

The Halting Problem

Gödel originally came up with a very ingenious proof of this, but I think that Turing's approach in some ways is more fundamental and easier to understand. I'm talking about the halting problem, Turing's fundamental theorem on the unsolvability of the halting problem, which says there is no mechanical procedure for deciding if a computer program will ever halt.

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.

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.

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 2N. 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.

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.

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.

Randomness in Arithmetic

So what is the result of using this technique of Jones and Matijasevic based on this remarkable theorem of Lucas?

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.

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.

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?

Further Reading