It is a great pleasure for me to be speaking today here in Vienna. It's a particularly great pleasure for me to be here because Vienna is where the great work of Gödel and Boltzmann was done, and their work is a necessary prerequisite for my own ideas. Of course the connection with Gödel was explained in Prof. Reichel's beautiful lecture. What may be a bit of a surprise is the name of Boltzmann. So let me talk a little bit about Boltzmann and the connection with my own work on randomness in mathematics.
You see, randomness in mathematics sounds impossible. If anything, mathematics is where there is least randomness, where there is most certainty and order and pattern and structure in ideas. Well, if you go back to Boltzmann's work, Boltzmann also put together two concepts which seem contradictory and invented an important new field, statistical mechanics.
I remember as a student reading those two words ``statistical mechanics,'' and thinking how is it possible---aren't these contradictory notions? Something mechanical is like a machine, predictable. What does statistics have to do with mechanics? These seem to be two widely separate ideas. Of course it took great intellectual courage on Boltzmann's part to apply statistical methods in mechanics, which he did with enormous success.
Statistical mechanics now is a fundamental part of physics. One forgets how controversial Boltzmann's ideas were when they were first proposed, and how courageous and imaginative he was. Boltzmann's work in many ways is closely connected to my work and to Gödel's work, which may be a little surprising.
I'm trying to understand Gödel's great incompleteness theorem, I'm obsessed with that. I believe that the full meaning of Gödel's result can be obtained by taking Boltzmann's ideas and applying them to mathematics and to mathematical logic. In other words, I propose a thermodynamical approach, a statistical-mechanics approach, to understanding the foundations of mathematics, to understanding the limitations and possibilities of mathematical reasoning.
Thermodynamics and statistical mechanics talk about what can be accomplished by machines, by heat engines, by steam engines, by physical systems. My approach to understanding the full implications of Gödel's work is mathematically analogous to the ideas of thermodynamics and Boltzmann and statistical mechanics. You might say, not completely seriously, that what I'm proposing is ``thermodynamical epistemology!''
What led me to all this? Well, I was absolutely fascinated by Gödel's theorem. It seemed to me that this had to be the most profound result, the most mysterious result, in mathematics. And I think that a key question that one should ask when one reads Gödel's enormously surprising result, is, well, how seriously should one take it?! It's clearly an enormously startling and unexpected result, but consider the mathematician working on normal mathematical questions. What is the meaning of Gödel for daily work in mathematics? That's the question I'd like to ask.
Gödel explicitly constructed an arithmetical assertion that is true but not provable within the system of Principia Mathematica of Russell and Whitehead. It's a very strange assertion. It's an enormously clever assertion: It says of itself, ``I'm unprovable!'' This is not the kind of assertion that one normally is interested in as a working mathematician. But of course a great part of Gödel's genius was to take such a bizarre question very seriously and also to clothe it as an arithmetical question. With the years this has led to the work on Hilbert's tenth problem, which is an even more straight-forward arithmetical incompleteness result inspired by Gödel's fundamental path-breaking work.
Let me make my question more explicit. There are many problems in the theory of numbers that are very simple to state. Are there an infinity of twin primes, primes that are two odd numbers separated by one even number? That question goes back a long way. A question which goes back to the ancient Greeks is, are there infinitely many even perfect numbers, and are there any odd perfect numbers?
Is it possible that the reason that these results have not been proven is because they are unprovable from the usual axioms? Is the significance of Gödel's incompleteness theorem that these results, which no mathematician has been able to prove, but which they believe in, should be taken as new axioms? In other words, how pervasive, how common, is the incompleteness phenomenon?
If I have a mathematical conjecture or hypothesis, and I work for a week unsuccessfully trying to prove it, I certainly do not have the right to say, ``Well obviously, invoking Gödel's incompleteness theorem, it's not my fault: Normal mathematical reasoning cannot prove this---we must add it as a new axiom!'' This extreme clearly is not justified.
When Gödel produced his great work, many important mathematicians like Hermann Weyl and John von Neumann took it as a personal blow. Their faith in mathematical reasoning was severely questioned. Hermann Weyl said it had a negative effect on his enthusiasm for doing mathematics. Of course it takes enormous enthusiasm to do good research, because it's so difficult. With time, however, people have gone to the other extreme, saying that in practice incompleteness has nothing to do with normal, every-day mathematics.
So I think it's a very serious question to ask, ``How common is incompleteness and unprovability?'' Is it a very bizarre pathological case, or is it pervasive and quite common? Because if it is, perhaps we should be doing mathematics quite differently.
One extreme would be experimental number theory, to do number theory as if it were physics, where one looks for conjectures by playing with prime numbers with a computer. For example, a physicist would say that the Riemann zeta hypothesis is amply justified by experiment, because many calculations have been done, and none contradicts it. It has to do with where the zeros of a function called the Riemann zeta function are. Up to now all the zeros are where Riemann said they were, on a certain line in the complex plane.
This conjecture has rich consequences. It explains a lot of empirically verified properties of the distribution of prime numbers. So it's a very useful conjecture. Now in physics, to go from Newtonian physics to relativity theory, to go from relativity theory to quantum mechanics, one adds new axioms. One needs new axioms to understand new fields of human experience.
In mathematics one doesn't normally think of doing this. But a physicist would say that the Riemann hypothesis should be taken as a new axiom because it's so rich and fertile in consequences. Of course, a physicist has to be prepared to throw away a theory and say that even though it looked good, in fact it's contradicted by further experience. Mathematicians don't like to be put in that position.
These are very difficult questions: How should one do mathematics? Should number theory be considered an experimental science like physics? Or should we forget about Gödel's result in our everyday work as mathematicians? There are many possibilities in this spectrum.
I think these are very difficult questions. I think it will take many years and many people to understand this fully. But let me tell you my tentative conclusion based on my ``thermodynamical'' approach. It's really an information-theoretic approach: The work of Boltzmann on statistical mechanics is closely connected intellectually with the work of Shannon on information theory and with my own work on algorithmic information theory. There's a clear evolutionary history connecting these ideas.
My approach is to measure how much information there is in a set of axioms, to measure how much information there is in a theorem. In certain circumstances I can show that if you have five pounds of axioms, only five pounds, but here is a ten-pound theorem, well this theorem is too big, it weighs too much to get from only five pounds of axioms.
Of course, I actually use an information-theoretic measure related to the Boltzmann entropy concept. Boltzmann would recognize some of the formulas in my papers, amazingly enough, because the interpretation is quite different: it involves computers and program size. But some of the formulas are identical. In fact, I like to use H for the same reason that Shannon used H, in honor of the Boltzmann H function, the H function dear to the heart of statistical physicists. (Of course, there's also a Hamiltonian H function, which is something else.)
The incompleteness phenomenon that Gödel discovered seems very natural from my information-theoretic point of view. You see, there is no self-reference. Gödel's incredibly clever proof skirts very very close to paradox. I was fascinated by it. I was also very disturbed by it as a child when I started thinking about all this.
If one measures information, then it seems natural to think, that if you want to get more information out, sometimes you have to put more information in. A physicist would say that it's natural that if one wants to encompass a wider range of mathematical experience, one needs to add additional axioms. To a physicist that doesn't seem outrageous. To a mathematician it's quite questionable and controversial.
So the point of view of algorithmic information theory suggests that what Gödel found is not an isolated singularity. The information-theoretic point of view suggests that Gödel's incompleteness phenomenon is very natural, pervasive and widespread. If this is true, perhaps we should be doing mathematics a little bit differently and a little bit more like physics is done.
Physicists always seem very pleased when I say this, and mathematicians don't seem at all pleased.
These are very difficult questions. I'm proposing this point of view, but by no means is it established. I think that one needs to study all this a lot more.
In summary, let me tell a story from ten years ago, from 1979, which was the centenary of Einstein's birth. There were many meetings around the world celebrating this occasion. And at one of them in New York I met a well-known physicist, John Wheeler. I went up to Wheeler and I asked him, ``Prof. Wheeler, do you think there's a connection between Gödel's incompleteness theorem and the Heisenberg uncertainty principle?'' Actually, I'd heard that he did, so I asked him, ``What connection do you think there is between Gödel's incompleteness theorem and Heisenberg's uncertainty principle?''
This is what Wheeler answered. He said, ``Well, one day I was at the Institute for Advanced Study, and I went to Gödel's office, and there was Gödel...'' I think Wheeler said that it was winter and Gödel had an electric heater and had his legs wrapped in a blanket.
Wheeler said, ``I went to Gödel, and I asked him, `Prof. Gödel, what connection do you see between your incompleteness theorem and Heisenberg's uncertainty principle?' '' I believe that Wheeler exaggerated a little bit now. He said, ``And Gödel got angry and threw me out of his office!'' Wheeler blamed Einstein for this. He said that Einstein had brain-washed Gödel against quantum mechanics and against Heisenberg's uncertainty principle!
In print I recently saw a for-the-record version of this anecdote (Jeremy Bernstein, Quantum Profiles, Princeton University Press, 1991, pp. 140-141), which probably is closer to the truth but is less dramatic. It said, not that Wheeler was thrown out of Gödel's office, but that Gödel simply did not want to talk about it since he shared Einstein's disapproval of quantum mechanics and uncertainty in physics. Wheeler and Gödel then talked about other topics in the philosophy of physics, and about cosmology.
There is some little-known work of Gödel connected with general relativity, some very interesting work, about universes where the past and the future is a loop, and you can travel into your past by going around. That's called a Gödel universe. It's a little-known piece of work that shows the stamp of Gödel's originality and profundity.
Okay, so what was the final conclusion of all this? I went up to Wheeler at this Einstein centenary meeting, and I asked him this question. Wheeler told me that he asked Gödel the same question, and Gödel didn't answer Wheeler's question, and Wheeler never answered my question! So I'm going to answer it!
I'll tell you what I think the connection really is between Gödel's incompleteness theorem and Heisenberg's uncertainty principle. To answer the question I want to make it a broader question. I would like to tell you what I think the connection is between incompleteness and physics.
I think that at the deepest level the implication of Gödel's incompleteness theorem is as I said before that mathematics should be pursued more in the spirit of physics, that that's the connection. I see some negative reactions from the audience! Which doesn't surprise me! Of course this is a difficult question and it's quite controversial. But that's what my work using an information-theoretic approach to Gödel suggests to me.
Number theory has in fact been pursued to a certain extent in the spirit of an experimental science. One could almost imagine a journal of experimental number theory. For example, there are papers published by number theorists which are, mathematicians say, ``modulo the Riemann hypothesis.'' That is to say, they're taking the Riemann hypothesis as an axiom, but instead of calling it a new axiom they're calling it a hypothesis.
There are many examples of how this information-theoretic point of view yields incompleteness results. I think the most interesting one is my recent work on randomness in arithmetic, which I haven't really referred to yet in my talk.
A fundamental question that many of us wonder about, especially as teenagers---that's an age particularly well-suited for fundamental questions---is the question, ``To what extent can the universe be comprehended by the human mind?'' Is the universe ordered? Is there chaos and randomness? Are there limits in principle to what we will ever be able to understand?
Hilbert stated very beautifully that he didn't believe that there were limits to what the human mind could accomplish in mathematics. He believed that every question could be resolved: either shown to be true or false. We might not be able to ever do it, but he believed that in principle it was possible. Any clear mathematical question would have a clear resolution via a mathematical proof. Of course, Gödel showed that this is not the case.
But it's really a more general question. Can the universe be comprehended, the physical universe as well as the universe of mathematical experience? That's a broader question.
To what extent can all this be comprehended by the human mind? We know that it cannot be completely comprehended because of Gödel's work. But is there some way of getting a feeling for how much can be comprehended? Again it boils down to that.
When I was a student at the university, I totally believed in science. But my faith in science was tried by the work I had to do in experimental physics laboratories. The experiments were difficult. It was hard for me to get good results. I'm sure some of you are excellent experimentalists. There are people who have a natural talent for doing physics experiments like there are people who have a natural talent for growing flowers. But for me, the physics laboratory was a difficult experience and I began to marvel that scientists had been able to create modern science in spite of the fact that Nature does not give a clear answer to questions that we ask in the laboratory. It's very difficult to get a clear answer from Nature as to how the world works.
So I asked myself, what is it that is the most convincing evidence, in our normal daily experience, that the universe can be comprehended, that there is law and order and predictability rather than chaos and arbitrary things which cannot be predicted and cannot be comprehended? In my experience I would say that what most convinces me in science and predictability and the comprehensibility of the universe is, you'll laugh, the computer!
I'm not referring now to the computer as an industrial gadget. I think the computer is really amazing not because of its practical usefulness, but because of the fact that it works! To get a physical system to behave so predictably over such long periods, over very extended calculations, is amazing when one thinks about it.
I've done calculations which involved billions (109) of successive operations each of which had to be accurately derived from the preceding ones. Billions of steps each of which depended on the preceding ones. I had ways of suspecting or predicting the final result or some characteristic of it, and it worked! It's really rather amazing. Of course, it doesn't always work, because the machine breaks down, or the programmer makes a mistake. But it works a lot of the time. And if one runs a program several times one usually gets the same answers.
It's really amazing when one thinks how many steps the machine is doing and how this chain of causal events is predictable and is understandable. That's the job of the computer engineer, to find physical principles that are as predictable as possible, that give him a physical way to model the predictability of mathematics. Because computers are actually mathematical machines, that is what they really are. At least a mathematician might say that.
So the computer is a wonderful example of predictability and a case where the physical behavior of a big chunk of the universe is very understandable and very predictable and follows definite laws. I don't know the detailed laws of how a transistor works. But the overall behavior of the system is amazingly comprehensible and predictable. Otherwise one would not use computers. They would be absolutely useless.
Now it may seem strange that starting with the computer one can construct what I believe to be a very dramatic example of randomness. This is an idea I got from the work of Turing, which in turn was inspired by the work of Gödel, both of which of course were responses to questions that Hilbert asked.
Turing asks, can one decide if a computer program will ever halt, if it will ever stop running? Turing took Cantor's diagonal argument from set theory and used it to show that there is no mechanical procedure for deciding if a computer program will ever halt.
Well, if one makes a small change in this, in Turing's theorem that the halting problem is undecidable, one gets my result that the halting probability is algorithmically random or irreducible mathematical information. It's a mathematical pun!
The problem with this theorem is of course that in doing everyday mathematics one does not worry about halting probabilities or halting problems. So I had the same problem that Gödel had when he was thinking about mathematical assertions which assert of themselves that they're unprovable. My problem was how to take this bizarre notion of a halting probability and convert it into an arithmetical assertion.
It turns out that one can do this: One can exhibit a way to toss a coin with whole numbers, with the integers, which are the bedrock of mathematics. I can show that in some areas of arithmetic there is complete randomness!
Don't misunderstand. I was interviewed on a BBC TV program. A lot of people in England think I said that 2 + 2 is sometimes 4, sometimes 5, and sometimes 3, and they think it's very funny! When I say that there is randomness in arithmetic I'm certainly not saying that 2 + 2 is sometimes 3 and sometimes 5. It's not that kind of randomness. That is where mathematics is as certain and as black and white as possible, with none of the uncertainties of physics.
To get complete randomness takes two steps.
The first step was really taken by Turing and is equivalent to Hilbert's tenth problem posed in 1900. One doesn't ask if 2 + 2 = 4 (we know the answer!). One asks if an algebraic equation involving only whole numbers, integers, has a solution or not.
Matijasevic showed in 1970 that this problem, Hilbert's tenth problem, is equivalent to Turing's theorem that the halting problem is undecidable: Given a computer program one can construct a diophantine equation, an algebraic equation in whole numbers, that has a solution if and only if the given computer program halts. Conversely, given a diophantine equation, an algebraic equation involving only whole numbers, one can construct a computer program that halts if and only if the given diophantine equation has a solution.
This theorem was proven by Matijasevic in 1970, but intellectually it can be traced directly back to the 1931 incompleteness theorem of Gödel. There were a number of people involved in getting this dramatic 1970 result. It may be viewed as Gödel's original 1931 result restated in much simpler arithmetical terms.
Unfortunately it turns out that this doesn't give complete randomness; it only gives partial randomness.
I'll now speak information-theoretically. Consider N cases of Hilbert's tenth problem. You ask, does the equation have a solution or not for N different equations? The worst would be if that were N bits of information, because each answer is independent. It turns out that it is only order of log2 N bits of information, because the answers are not at all independent. That's very easy to see, but I can't go into it.
So what does one do to get completely independent mathematical facts in elementary arithmetic? It's very simple. One goes a step farther: Instead of taking the halting problem and making it into the question of whether a diophantine equation has a solution or not, one takes my halting probability, and makes it into the question of whether a diophantine equation has a finite or an infinite number of solutions.
If the equations are constructed properly, whether they have a finite or an infinite number of solutions is completely random. In fact, a single equation with a parameter will do. One takes the parameter to be 1, 2, 3, 4, 5, ... and one gets a series of derived equations from the original equation by fixing the value of the parameter. For each of these derived equations one asks: ``Is there a finite or an infinite number of solutions?'' I can construct this equation in such a way that the answers to this question are independent irreducible mathematical facts.
So that is how you use arithmetic to toss a coin, to give you randomness.
By the way, this equation turns out to be about 200 pages long and has 17,000 variables, and it's fun to calculate it. But one doesn't do it by hand! One does it with a computer. A computer is essential to be able to exhibit this equation.
It is an infinite series of equations really, each of which has a different value of the parameter. We ask whether each of the equations has a finite or an infinite number of solutions. Exactly what does it mean to say that these are irreducible mathematical facts?
Well, how does one reduce mathematical facts? To axioms, to postulates! And the inverse of the reduction is to prove a theorem, I mean, to expand axioms into theorems. The traditional notion of mathematics is that a small finite set of axioms can give us all of mathematics, all mathematical truths. That was the pre-Gödel notion that Hilbert believed in.
So in a sense what we're doing is we're compressing a lot of mathematical facts enormously, into a small set of axioms. Or actually, we're expanding a finite set of axioms into individual mathematical facts.
I'm asserting that I've constructed irreducible mathematical facts. What does this mean? It means that you cannot shrink them any more, you cannot squeeze them into axioms. In fact, that these are irreducible mathematical assertions means that essentially the only way to prove them is if we directly take each individual assertion that we wish to prove as an axiom! That's cheating!
Yes, one can always prove an assertion by putting the assertion itself as a new axiom, but then we're not using reasoning. Picking new axioms is not deduction; it's the kind of thing that physicists worry about.
It is surprising that we can have an infinite number of independent mathematical facts that can only be proven by taking them as axioms. But if we think about coin tossing this is not at all surprising. You see, the notion of independent coin tosses is exactly like that.
Each time one tosses a fair coin, whether the outcome of that particular toss is head or tails, tells us absolutely nothing about the outcome of any future toss, and absolutely nothing about the outcome of any previous toss. That's how casinos make money: There is no way to predict from what has happened at a roulette wheel what is going to happen. Well, there is if the roulette wheel isn't balanced, and of course the casino works hard to make sure that the roulette wheel is working properly.
Let's go back to coin tossing, to the notion that a series of tosses has no structure. Even if one knew all the even results, it wouldn't help us predict any of the odd results. Even if one knew the first thousand tosses, that wouldn't help us predict the thousand-first toss.
Well, it's the same with using my equation to get randomness. Even if somehow one were told for all the even cases, whether there are a finite or an infinite number of solutions, this would be absolutely no help in getting the odd cases. Even if one were told the first thousand cases, whether there are a finite or an infinite number of solutions, it would be no help in getting the thousand-first case.
In fact I don't see how one could ever get any of the cases. Because there is absolutely no structure or pattern, and as I said these are irreducible mathematical facts. Essentially the only way to prove them is to directly assume them, which is not using reasoning at all.
So we've gone a long way in less than a hundred years: From Hilbert's conviction that every mathematical problem can be settled decisively by mathematical reasoning, to Gödel's surprising discovery that any finite set of axioms for elementary arithmetic is incomplete, to a new extreme, areas of arithmetic where reasoning is totally impotent and totally irrelevant.
Some people were depressed by Gödel's result. You might say, ``This is all rather upsetting; should I switch fields and stop studying mathematics?'' I certainly don't think you should!
You see, even though there is no pattern or structure in the question of whether individual cases of my equation have a finite or an infinite number of solutions, one can deal with it statistically: It turns out that in half the cases there's a finite number of solutions, and in half the cases there's an infinite number of solutions.
It's exactly like coin tosses, independent fair coin tosses. One can use statistical methods and prove theorems about the statistical patterns and properties of the answers to the question, which cannot be answered in each particular case, of whether there are a finite or an infinite number of solutions.
Let me repeat that the answers have a very simple statistical structure, that of independent tosses of a fair coin. So half the cases are heads and half are tails, one-fourth are a head followed by a head, one-fourth a head followed by a tail, one-fourth tail-head, one-fourth tail-tail, and so on for larger blocks and all the other statistical properties that one would like.
This kind of situation is not new; it's happened before, in physics. In quantum mechanics the Schrödinger equation shows this very clearly. The Schrödinger equation does not directly predict how a physical system will behave. The Schrödinger psi function is only a probability. We can solve the Schrödinger equation to determine the probability that a physical system will behave in a certain way. The equation does not tell us what the system will do, it tells us the probability that it will do certain things.
In the 1920's and 1930's, this was very controversial, and Einstein hated it. He said, ``God doesn't play dice!'' But as you all know and as Prof. Reichel explained, in recent times this lack of predictability has spread outside quantum mechanics. It turns out that even classical physics, Newtonian physics, contains unpredictability and randomness.
This is the field of non-linear dynamics or ``deterministic chaos.'' It occurs in situations where small changes can produce big effects, in non-linear situations, very unstable situations, like the weather. It turns out that the weather is unpredictable, even in principle, as Prof. Casti discusses in his forthcoming book (John L. Casti, Searching for Certainty---What Scientists Can Know About the Future, William Morrow, New York, 1991). He studies the question of predictability and comprehensibility in a very broad context, including mathematics, the weather, and economics.
So it begins to look now like randomness is a unifying principle. We not only see it in quantum mechanics and classical physics, but even in pure mathematics, in elementary number theory. As I said before, I don't think that this should be viewed pessimistically. What it suggests to me, is that pure mathematics has much closer ties with physics than one suspected. Perhaps Plato's universe of mathematical ideas and the physical universe that we live in when we're not doing mathematics, perhaps these are closer to each other than has hitherto been suspected.
Thank you.