I've been learning some biology at this meeting, but what can I contribute to the discussion? The answer is, not much. I do discrete mathematics, in fact, metamathematics. In my work I use a notion of complexity, and it would be great if this complexity concept had something to do with biology. Unfortunately it doesn't.
Biology deals with very complicated systems, but I don't think my work on complexity can be applied to biology. Instead I've taken the idea of complexity from biology and I'm using it to try to understand what mathematics can and cannot achieve. That's called metamathematics. So in this talk you are going to see an idea from biology applied in an unexpected way.
My story begins about a century ago with David Hilbert, a famous German mathematician, who believed that mathematical truth is absolutely rigorous, completely black or white, never gray. And he wanted to demonstrate that in the most clear-cut, straightforward possible way. He wanted to formalize all of mathematics.
Hilbert was responding to problems in the foundations of mathematics provoked by Cantor's theory of infinite sets. There were many paradoxes, paradoxes discussed by such people as Bertrand Russell and Frege and many others. Hilbert's proposal for dealing with this crisis was formalism.
Hilbert's plan for avoiding contradictions and paradoxes in mathematics was to make mathematical reasoning extremely precise. He believed that mathematics is absolute truth, totally black or white. Therefore, he reasoned, it ought to be possible for us all to agree on a finite set of axioms to use as the basis for all of math. And we should use symbolic logic, not a natural language, because natural languages are ambiguous.
In other words, Hilbert's goal was to formalize mathematics completely, to set up an axiomatic system in the style of Euclid, but for all of mathematics. His plan was to write down a list of axioms, using formal logic, for all of mathematics. And once we all agree on the rules of logic and on the axioms, then this will once and for all clarify what mathematics is, and how things should be done. Math will consist of everything you can prove from those axioms using these rules of logic.
The goal was to make everything completely objective, and to eliminate all subjectivity from mathematics. If somebody claims that they have a proof, done in this very formal way, with no missing steps, then it's completely mechanical to check whether the proof is correct or not. A machine can do it. You don't need any human referees. Well, you do need referees to say if the result is worth publishing, but you don't need anybody to check whether the proof is correct or not.
So this was Hilbert's idea. And once he found the correct rules of logic and the right list of axioms, he would then have to convince people that this was a good system that we should all use, and that it avoids all the paradoxes. So Hilbert's project was rather ambitious. But it starts with the simple idea that if mathematics really provides absolute truth, then it ought to be possible to formalize everything in precisely this way.
Some people really hated David Hilbert's idea. Since Hilbert was a German, you will not be surprised to hear that one of his severest critics was a Frenchman, Henri Poincaré. Poincaré compared Hilbert's proposal with that mythical Chicago machine --- this was when Chicago had enormous slaughterhouses --- where pigs go in one end of the machine and out come neatly wrapped sausages at the other end. Is mathematics just a sausage-making machine? Poincaré didn't think that it was, not at all.
But Poincaré's caustic remarks didn't deter Hilbert and his disciples.
So what happened next?
Well, for about thirty years it looked like Hilbert was making progress and would eventually succeed in carrying out this project. Then disaster struck...
Let me say, by the way, that Hilbert's formalist, axiomatic style survives in the Bourbaki school, which even though Bourbaki is now gone, is still very influential. Bourbaki was a group of French mathematicians who were traitors to French mathematics, because they preferred Hilbert's Prussian approach to Poincaré's. Even though Bourbaki has now disbanded, formalization's icy grip still rules mathematics, and this comes from Hilbert. The current fashion is that ideally a math paper should have no words, no diagrams, no examples, and no discussion of history or motivation, a very formalist view indeed.
Okay, so this was Hilbert's idea. But it was initially viewed as a good idea, because Hilbert didn't say that people should actually work in a logical language and publish machine-checkable proofs. The real goal was to make mathematics absolutely certain, completely rigorous. And most mathematicians thought that this ought to be possible since mathematical arguments are much more convincing than arguments in physics or in law.
So despite Poincaré's remarks, Hilbert's project sounded like a good idea, and a number of mathematicians worked on it for about thirty years. And then in 1931 in Vienna, Kurt Gödel, who initially was working to carry out Hilbert's program, showed that it couldn't be done. This is the famous 1931 incompleteness theorem of Kurt Gödel. The basic idea is that ``I'm unprovable'' is provable if and only if it's false.
I have only thirty minutes, so I'm not going to be able to explain Gödel's proof. It shows that Hilbert's program can't work, because the first step was to come up with an axiomatic system for all of math (and then to convince people to use it by showing that you don't get the contradictions and paradoxes that were bothering mathematicians). But what Gödel showed is that no finite set of axioms, no formal axiomatic theory, can include everything --- there is no theory of everything for pure mathematics. That's what Gödel showed.
This was quite a shock, and in 1936 Alan Turing made things even worse. Turing found a much deeper reason for incompleteness. This is in Turing's famous 1936 paper ``On computable numbers, with an application to the Entscheidungsproblem.'' In a way, Turing's 1936 paper creates the computer industry, because it talks about flexible, universal machines and the idea of hardware and software. And besides constructing a primitive kind of computer called a Turing machine, this paper introduces the idea of the computer to pure mathematics as a fundamental new concept.
However, I think that the most interesting thing about this paper isn't its positive aspect, it's its negative aspect. The negative aspect of the paper is that Turing shows that there are very basic things which cannot be computed. And from uncomputability --- from the existence of mathematical questions where you cannot calculate the answers systematically --- Turing deduces a form of incompleteness, a new kind of incompleteness theorem.
You see, if Hilbert had been right, and you had a formal axiomatic system for all of math, you could systematically run though the tree of all possible proofs. This would be very slow, but in principle you could systematically look at all one-step proofs, two step proofs, three step proofs, and that way you could mechanically generate all the theorems starting from the axioms. And if you wanted to see whether something is true or not, you just do that until either you find a proof that the result you're interested in is true, or you find a proof that the result you're interested in is false. This is why Poincaré mocked Hilbert's project saying that it would make mathematics into a sausage machine.
What Turing showed in 1936 is that there can't be such a sausage machine, because there are mathematical questions where you can't systematically calculate the answer, and therefore you can't prove what the answer is either, not in all individual cases. Because if you could, then you could run through all possible proofs until you either find a proof that the answer is ``yes'' or that the answer is ``no,'' and this would give you a mechanical procedure, an algorithm, for always calculating the answer, which however cannot exist because of uncomputability. So incompleteness is a corollary of uncomputability.
Turing's work is wonderful because it makes incompleteness much more solid. Gödel's proof was too paradoxical: ``I'm unprovable'' is too much like ``This statement is false.'' Gödel's proof looks too close to the paradoxes which were upsetting everybody. But Turing found a more basic reason that you can't have a formal theory for all of mathematics.
What about my own work? I haven't mentioned that yet.
What I've tried to add to this discussion of incompleteness is some kind of a notion of complexity. What's complexity? Well, there's certainly a lot of complexity in biological systems. At this meeting we've seen lots of examples of how amazingly complex some basic biological mechanisms are. But how do you define complexity? Well, there's lots of ways of defining complexity. And in fact you biologists don't give a precise definition, you just sort of know. You can recognize it when you see it.
But I'm a mathematician, so my idea was a definition of complexity that may not be useful in biology, but which I can use in metamathematics. I just look at the size of computer programs. I say that something has N bits of complexity if you need an N-bit program to calculate it. This is a very straightforward definition. I don't care how long this N-bit program takes to run. If the smallest program that calculates something is exactly a thousand bits long, I don't care if that program goes on working for billions and billions of years, as long as it finally yields the thing I'm interested in.
This is a very simple-minded measure of complexity that is not intended for use in practical applications. It's intended to apply in pure math. So what can you do with this idea, with this toy notion of complexity? I think it enables you to compare biology and mathematics. But first let me compare physics and biology, they're two extremes.
Theoretical physics is very beautiful because it's based on a small bunch of simple, elegant equations for the laws of physics. And most physicists hope to someday find a theory of everything, a set of equations which you can put on a T-shirt, otherwise what's the point, right? So that's what fundamental physics looks like.
Now let's contrast this with the situation in biology. Biology is very complicated and fascinating and full of surprises. You are never going to find a simple equation for your wife, for a human society, for the global economy, or for that enormous table of the catalytic reactions in the metabolism in every single cell. Biology is not at all like fundamental physics. In biology there are no simple equations. Biology is complicated, it's messy, it works.
Now let's look at pure mathematics, and see how it compares with physics at one extreme, a simple fundamental theory that applies to everything, and with biology, where things are very complicated, very surprising, very diverse, very messy. Well, obviously mathematics co-evolved with physics, right? Normally, you'd think that mathematics must be like theoretical physics, and that's what Hilbert thought. You know, one of the reasons I'm a pure mathematician rather than a biologist is that I don't have a good memory. French was my worst subject, but I could do well whenever there are a few fundamental principles and then in each individual case you have to derive the consequences. I could do that on the spot, but I was awful at remembering things.
But is mathematics really simple and elegant like physics? Surprisingly enough, using this idea of complexity that I sort of borrowed from biology, I can not only show that pure math is like biology, in fact it's even worse than biology, because it's infinitely complex, provably infinitely complex.
To repeat, physics, that's the idea of a simple theory for the entire universe, that's the idea that the universe looks complicated but is really very simple. And you show that by giving the equations, and presumably simple initial conditions, and then the big bang takes off, so in principle you can calculate the time-evolution of the entire universe step by step using the laws of physics. But in biology you don't expect things to be simple, you expect things to be wonderfully rich, complicated, frozen accidents, bricolage, things patched on top of other things.
How can I show that mathematics is closer to biology than to physics? Well, like this. Turing considers a problem that's called the halting problem. This is actually the basic idea in his 1936 paper. The halting problem is to decide in advance if a self-contained computer program will eventually stop. And the fundamental mathematical result in Turing's 1936 paper is that there is no general algorithmic solution to the halting problem. (This is how Turing shows that there are important things which can't be calculated.)
There's no way to calculate in advance whether a computer program will go on forever or will eventually stop. Of course, you can start running the program, and if it stops, you know it's stopped. But there is no general way to know at what point to give up and decide that you already gave it enough time, and if it hasn't halted yet, it's never going to. I'm talking about self-contained computer programs.
This is Turing's fundamental result. Now I'm going to change things a little bit. Instead of talking about individual computer programs, consider all possible computer programs, put them all in a bag, shake it well, close your eyes, pick a random computer program, and ask, what is the probability this computer program eventually halts. I call this number the halting probability Ω. It's a number between zero and one.
If every computer programs halts, then the halting probability Ω is one. If no computer program halts, if they all search endlessly, then the halting probability Ω is zero. And since in actual fact some computer programs halt and some never halt, the halting probability is greater than zero and less than one.
This number Ω is very simply defined, it's just a probability, not a big deal. But it turns out that you cannot know the numerical value of Ω, you can't calculate it, because it's extremely valuable information and would enable you to answer many, many important mathematical questions.
I always think of writing out Ω in binary, in base-two, and of the infinite sequence of bits that come after the decimal point. These bits turn out to be incredibly valuable, because you can show that they are the most compressed way of giving answers to the halting problem. The bits of Ω are the best possible oracle for the halting problem.
What does Ω have to do with oracles? Well, supposing you could ask God yes/no questions, and you want to bother him as little as possible, the best thing to do is not to ask about individual cases of the halting problem. The best way to get answers to the halting problem is to ask what are the initial bits of the halting probability. Ω is the diamond you get by compressing the coal of Turing's halting problem. Once you get rid of all the redundancy, it's not surprising that what comes out looks random, because once you eliminate all the redundancy from anything, what's left doesn't have any structure. If it had any structure, then we could compress it some more.
In the definition of the halting probability Ω, how do I pick a program at random? Well, the computer programs are written in binary, and for every bit of the program you do an independent toss of a fair coin. So each N-bit program that halts contributes 2−N to the halting probability Ω. And for this to work and give a finite sum instead of diverging to infinity, it's important to use self-delimiting programs. In other words, no extension of a valid program is a valid program. But this is rather technical and I don't have time to explain it.
Okay, so this number Ω, its bits look completely random. In fact, according to classical Shannon information theory, anything that's been compressed as much as possible seems structureless or random, for example, Gaussian noise. Because if there were any structure, you could use that to compress the information more. In fact, if you use a file-compression program on a computer, for example, LZW compression, the stuff that comes out may be your precious file, but it looks pretty meaningless once you've compressed it, because if it didn't, that means the compression program didn't do a good job.
Now I come to the punch line of my talk. The point of all this is that the bits of the number Ω are an example of irreducible complexity. They are maximally unknowable information in pure mathematics itself. In a way the bits of Ω are the DNA for all of mathematics. And they're the proof that mathematics is infinitely complex, and therefore even worse than biology. Biology is enormously complex, but it has finite complexity. But pure math, I can prove that that has infinite complexity.
Let me explain this better. Let's say you want to calculate, you want to know the numerical value of Ω with a certain degree of precision, say, N bits of precision. You want to know the first N bits after the decimal point, which amounts to knowing the numerical value of Ω to one part in 2N. To be able to calculate those first N bits, you unfortunately will need to use an N-bit program. So you might as well just write them out from a table without doing any calculating.
If I wanted to misuse Kantian terminology, I would say ``the thing in itself'' is the only way to comprehend the bits of Ω. You can exhibit them, but you can't really calculate them.
Let me explain this differently. Why are the bits of Ω maximally unknowable and infinitely complex? Well, let's say that you have a formal mathematical theory which enables you to prove that, say, the tenth bit of Ω is a 1, or that the ninety-ninth bit of Ω is a 0. Well, any mathematical theory that enables you to prove what are the values of the first N bits of the halting probability, has to have N bits of axioms.
Of course, you can have an axiom that directly tells you what the first N bits of the halting probability are. Anything can be proved if you are willing to add it as a new axiom. But in the case of Ω, that's the only way to proceed, that's the only way to be able to use mathematical proof to determine the first N bits. In other words, Ω has irreducible complexity. The only way to get N bits of Ω out of a mathematical theory is to put all that complexity in, which means you're not using reasoning. You can prove anything by adding it as a new axiom, and in this case that is the very best you can do.
Every one of these bits is an independent atomic mathematical fact, it's one bit of mathematical creativity. Every one of these bits is a complete surprise. It's a mathematical fact which has no connection with any other mathematical fact, or at least with any other bit of Ω. In other words, if you knew the first million bits of the halting probability, it wouldn't help you to get the next bit. If you knew all the even bits, it wouldn't help you to get any of the odd bits. It's very much like independent tosses of a fair coin, even though Ω is mathematically defined in a very straightforward way.
So this is a place where mathematical truth is irreducible. What I've basically done is I've gotten irreducible complexity by compressing all the redundancy out of individual cases of Turing's halting problem. Once you remove all the redundancy, it's not surprising that what you have left cannot be compressed any more and is irreducibly complex. What this all shows is that if you're interested in the value of individual bits of Ω, then you're in big trouble.
Of course, one possible reaction to all of this is ``Well, I don't care about the halting probability!'' But since Ω is part of pure math and is irreducibly complex, and it's an infinite number of bits, this shows that pure math as a whole is infinitely complicated, and therefore in a sense even worse than biology.
Okay, how has the world of mathematics adjusted to all of this? Well, the basic answer is that nobody wants to hear this message, and pure mathematicians go on as if Hilbert were right, and as if Bourbaki were still in fashion.
What about Gödel and Turing? What do they think are the consequences of their own work? What do they think all this says about the human mind and human capabilities?
Gödel himself did not think that the incompleteness theorem limits the capability of human mathematicians. Gödel's view is that human beings have a divine spark which enables them to directly intuit mathematical truth, to directly perceive the Platonic world of mathematical ideas. Gödel has faith that if a mathematical question is important, using this divine spark, mathematicians will eventually be able to settle it. He disagrees with the standard interpretation of his result, as showing limitations on what human beings can achieve. Rebecca Goldstein explains this very well in her book on Gödel called Incompleteness.
What about Turing? Turing is a very different kettle of fish. Turing wrote one of the famous papers on artificial intelligence, in fact, one of the first papers on artificial intelligence. Turing believed that human beings are machines, and that computers can be programmed to think like a human being. No divine spark, none at all!
I don't know whether we have a divine spark or we're just machines, I think maybe there's a little bit of both. And therefore I think that it's important that each individual make a decision, you know, which do you prefer, and does their best to do something about it.
14 February 2008