Today I'm not going to talk much about Ω. I will focus on that at Wilfrid Laurier University tomorrow. And if you want to hear a little bit about my current enthusiasm, which is what I'm optimistically calling metabiology --- it's a field with a lovely name and almost no content at this time --- that's on Wednesday at the Institute for Quantum Computing.
I thought it would be fun here at the Perimeter Institute to repeat a talk, to give a version of a talk, that I gave in Jerusalem a year ago. To understand the talk it helps to keep in mind that it was first given in Jerusalem. I'd like to give you a broad sweep of the history of mathematical logic. I'm a mathematician who likes physicists; some mathematicians don't like physicists. But I do. Before I became a mathematician I wanted to be a physicist.
So I'm going to talk about mathematics, and I'd like to give you a broad overview, most definitely a non-standard view of some intellectual history. It will be a talk about the history of work on the foundations of mathematics as seen from the perspective of the Middle Ages. So here goes...
There is a wonderful book by Umberto Eco called The Search for the Perfect Language, and I recommend it highly to all of you.
In The Search for the Perfect Language you can see that Umberto Eco likes the Middle Ages --- I think he probably wishes we were still there. And this book talks about a dream that Eco believes played a fundamental role in European intellectual history, which is the search for the perfect language.
What is the search for the perfect language? Nowadays a physicist would call this the search for a Theory of Everything (TOE), but in the terms in which it was formulated originally, it was the idea of finding, shall we say, the language of creation, the language before the Tower of Babel, the language that God used in creating the universe, the language whose structure directly expresses the structure of the world, the language in which concepts are expressed in their direct, original format.
You can see that this idea is a little bit like the attempt to find a foundational Theory of Everything in physics.
The crucial point is that knowing this language would be like having a key to universal knowledge. If you're a theologian, it would bring you closer, very close, to God's thoughts, which is dangerous. If you're a magician, it would give you magical powers. If you're a linguist, it would tell you the original, pure, uncorrupted language from which all languages descend. One can go on and on...
This very fascinating book is about the quest to find this language. If you find it, you're opening a door to absolute knowledge, to God, to the ultimate nature of reality, to whatever.
And there are a lot of interesting chapters in this intellectual history. One of them is Raymond Lull, around 1200, a Catalan.
Let's leave Lull and go on to Leibniz. In The Search for the Perfect Language there is an entire chapter on Leibniz. Leibniz is a transitional figure in the search for the perfect language. Leibniz is wonderful because he is universal. He knows all about Kabbalah, Christian Kabbalah and Jewish Kabbalah, and all kinds of hermetic and esoteric doctrines, and he knows all about alchemy, he actually ghost-authored a book on alchemy. Leibniz knows about all these things, and he knows about ancient philosophy, he knows about scholastic philosophy, and he also knows about what was then called mechanical philosophy, which was the beginning of modern science. And Leibniz sees good in all of this.
And he formulates a version of the search for the perfect language, which is firmly grounded in the magical, theological original idea, but which is also fit for consumption nowadays, that is, acceptable to modern ears, to contemporary scientists. This is a universal language he called the characteristica universalis that was supposed to come with a crucial calculus ratiocinator.
So this is Leibniz's version of the search for the perfect language. How far did he get with this?
Well, Leibniz is a person who gets bored easily, and flies like a butterfly from field to field, throwing out fundamental ideas, rarely taking the trouble to develop them fully.
One case of the characteristica universalis that Leibniz did develop is called the calculus. This is one case where Leibniz worked out his ideas for the perfect language in beautiful detail.
Leibniz's version of the calculus differs from Newton's precisely because it is part of Leibniz's project for the characteristica universalis. Christian Huygens hated the calculus.
Christian Huygens taught Leibniz mathematics in Paris at a relatively late age, when Leibniz was in his twenties. Most mathematicians start very, very young. And Christian Huygen's hated Leibniz's calculus because he said that it was mechanical, it was brainless: Any fool can just calculate the answer by following the rules, without understanding what he or she is doing.
Huygens preferred the old, synthetic geometry proofs where you have to be creative and come up with a diagram and some particular reason for something to be true. Leibniz wanted a general method. He wanted to get the formalism, the notation, right, and have a mechanical way to get the answer.
Huygens didn't like this, but that was precisely the point. This was precisely what Leibniz was looking for, for everything!
The idea was that if you get absolute truth, if you have found the truth, it should mechanically enable you to determine what's going on, without creativity. This is good, this is not bad.
This is also precisely how Leibniz's version of the calculus differed from Newton's. Leibniz saw clearly the importance of having a formalism that led you automatically to the answer.
Let's now take a big jump, to David Hilbert, about a century ago... No, first I want to tell you about an important attempt to find the perfect language: Cantor's theory of infinite sets.
This theory of infinite sets was actually theology. This is mathematical theology. Normally you don't mention that fact. To be a field of mathematics, the price of admission is you throw out all the philosophy, and you just end up with something technical. So all the theology has been thrown out.
But Cantor's goal was to understand God. God is transcendent. The theory of infinite sets has this hierarchy of bigger and bigger infinities, the alephs, the ℵ's. You have ℵ0, ℵ1, the infinity of integers, of real numbers, and you keep going. Each one of these is the set of all subsets of the previous one. And very far out you get mind-boggling infinities like ℵω; this is the first infinity after
Then you can continue with
You know, God is very far off, since God is infinite and transcendent. We can try to go in His direction. But we're never going to get there, because after every cardinal, there's a bigger one, the cardinality of the set of all subsets. And after any infinite sequence of cardinals that you get, you just take the union of all of that, and you get a bigger cardinal than is in the sequence. So this thing is inherently open-ended. And contradictory, by the way!
There's only one problem. This is absolutely wonderful, breath-taking stuff. The only problem is that it's contradictory.
The problem is very simple. If you take the universal set, the set of everything, and you consider the set of all its subsets, by Cantor's diagonal argument this should have a bigger cardinality, but how can you have anything bigger than the set of everything?
This is the paradox that Bertrand Russell discovered. Russell looked at this and asked why do you get this bad result. And if you look at the Cantor diagonal argument proof that the set of all subsets of everything is bigger than everything, it involves the set of all sets that are not members of themselves,
Cantor was aware of the fact that this happens, but Cantor wasn't bothered by these contradictions, because he was doing theology. We're finite but God is infinite, and it's paradoxical for a finite being to try to comprehend a transcendent, infinite being, so paradoxes are okay. But the math community is not very happy with a theory which leads to contradictions.
However, these ideas are so wonderful, that what the math community has done is forget about all this theology and philosophy and try to sweep the contradictions under the rug. There is an expurgated version of all this called Zermelo-Fraenkel set theory, with the axiom of choice, usually: ZFC. This is a formal axiomatic theory which you develop using first-order logic, and it is an expurgated version of Cantor's theory believed not to contain any paradoxes.
Anyway, Bertrand Russell was inspired by all of this to attempt a general critique of mathematical reasoning, and to find a lot of contradictions, a lot of mathematical arguments that lead to contradictions.
Russell was an atheist who was searching for the absolute, who believed in absolute truth. And he loved mathematics and wanted mathematics to be perfect. Russell went around telling people about these contradictions in order to try to get them fixed.
Besides the paradox that there's no biggest cardinal and that the set of subsets of everything is bigger than everything, there's also a problem with the ordinal numbers that's called the Burali-Forti paradox, namely that the set of all the ordinals is an ordinal that's bigger than all the ordinals. This works because each ordinal can be defined as the set of all the ordinals that are smaller than it is. (Then an ordinal is less than another ordinal if and only if it is contained in it.)
Russell is going around telling people that reason leads to contradictions. So David Hilbert about a century ago proposes a program to put mathematics on a firm foundation. And basically what Hilbert proposes is the idea of a completely formal axiomatic theory, which is a modern version of Leibniz's characteristica universalis and calculus ratiocinator:
So in such a formal axiomatic theory you would have a finite number of axioms, axioms that are not written in an ambiguous natural language. Instead you use a precise artificial language with a simple, regular artificial grammar. You use mathematical logic, not informal reasoning, and you specify the rules of the game completely precisely. It should be mechanical to decide whether a proof is correct.
Hilbert was a conservative. He believed that mathematics gives absolute truth, which is an idea from the Middle Ages. You can see the Middle Ages whenever you mention absolute truth. Nevertheless, modern mathematicians remain enamored with absolute truth. As Gödel said, we pure mathematicians are the last holdout of the Middle Ages. We still believe in the Platonic world of ideas, at least mathematical ideas, when everyone else, including philosophers, now laughs at this notion. But pure mathematicians live in the Platonic world of ideas, even though everyone else stopped believing in this a long time ago.
So math gives absolute truth, said Hilbert. Every mathematician somewhere deep inside believes this. Then there ought to exist a finite set of axioms, and a precise set of rules for deduction, for inference, such that all of mathematical truth is a consequence of these axioms. You see, if mathematical truth is black or white, and purely objective, then if you fill in all the steps in a proof and carefully use an artificial language to avoid ambiguity, you should be able to have a finite set of axioms we can all agree on, that in principle enable you to deduce all of mathematical truth. This is just the notion that mathematics provides absolute certainty; Hilbert is analyzing what this means.
What Hilbert says is that the traditional view that mathematics provides absolute certainty, that in the Platonic world of pure mathematics everything is black or white, means that there should be a single formal axiomatic theory for all of math. That was a very important idea of his.
An important consequence of this idea goes back to the Middle Ages. This perfect language for mathematics, which is what Hilbert was looking for, would in fact give a key to absolute knowledge, because in principle you could mechanically deduce all the theorems from the axioms, simply by running through the tree of all possible proofs. You start with the axioms, then you apply the rules of inference once, and get all the theorems that have one-step proofs, you apply them two times, and you get all the theorems that have two-step proofs, and like that, totally mechanically, you would get all of mathematical truth, by systematically traversing the tree of all possible proofs.
This would not put all mathematicians out of work, not at all. In practice this process would take an outrageous amount of time to get to interesting results, and all the interesting theorems would be overwhelmed by uninteresting theorems, such as the fact that 1 + 1 = 2 and other trivialities.
It would be hard to find the interesting theorems and to separate the wheat from the chaff. But in principle this would give you all mathematical truths. You wouldn't actually do it, but it would show that math gives absolute certainty.
By the way, it was important to make all mathematicians agree on the choice of formal axiomatic theory, and you would use metamathematics to try to convince everyone that this formal axiomatic theory avoids all the paradoxes that Bertrand Russell had noticed and contains no contradictions.
Okay, so this was the idea of putting mathematics on a firm foundation and removing all doubts. This was Hilbert's idea, about a century ago, and metamathematics studies a formal axiomatic theory from the outside, and notice that this is a door to absolute truth, following the notion of the perfect language.
So what happens with this program, with this proposal of Hilbert's? Well, there's some good news and some bad news. Some of the good news I already mentioned: The thing that comes the closest to what Hilbert asked for is Zermelo-Fraenkel set theory, and it is a beautiful axiomatic theory. I want to mention some of the milestones in the development of this theory.
One of them is the von Neumann integers, so let me tell you about that. Remember that Spinoza has a philosophical system in which the world is built out of only one substance, and that substance is God, that's all there is. Zermelo-Fraenkel set theory is similar. Everything is sets, and every set is built out of the empty set. That's all there is: the empty set, and sets built starting with the empty set.
So zero is the empty set, that's the first von Neumann integer, and in general n + 1 is defined to be the set of all integers less than or equal to n:
Then you can define rational numbers as pairs of these integers, you can define real numbers as limit sequences of rationals, and you get all of mathematics, starting just with the empty set. So it's a lovely piece of ontology. Here's all of mathematical creation just built out of the empty set.
And other people who worked on this are of course Fraenkel and Zermelo, because it is called Zermelo-Fraenkel set theory, and an approximate notion of what they did was to try to avoid sets that are too big. The universal set is too big, it gets you into trouble. Not every property determines a set.
So this is a formal theory that most mathematicians believe enables you to carry out all the arguments that normally appear in mathematics --- maybe if you don't include category theory, which is very difficult to formalize, and even more paradoxical than set theory, from what I hear.
Okay, so that's some of the positive work on Hilbert's program. Now some of the negative work on Hilbert's program --- I'd like to tell you about it, you've all heard of it --- is of course Gödel in 1931 and Turing in 1936.
And this is Gödel's incompleteness theorem of 1931, and Gödel's original proof is very strange. It's basically the paradox of ``this statement is false,''
If it's provable, then we're proving something that's false, because it says it's unprovable. So we hope that's not the case; by hypothesis, we'll eliminate that possibility. If we prove things that are false, we have a formal axiomatic theory that we're not interested in, because it proves false things.
The only possibility left is that it's unprovable. But if it's unprovable then it's true, because it asserts it's unprovable, therefore there's a hole. We haven't captured all of mathematical truth in our theory.
This proof of incompleteness shocks a lot of people, but my personal reaction to it is, okay, it's correct, but I don't like it.
A better proof of incompleteness, a deeper proof, comes from Turing in 1936. He derives incompleteness from a more fundamental phenomenon, which is uncomputability, the discovery that mathematics is full of stuff that can't be calculated, of things you can define, but which you cannot calculate, because there's no algorithm.
Why not? Because if there were a formal axiomatic theory that's complete for the halting problem, that would give you a mechanical procedure for deciding, by running through the tree of all possible proofs, until you find a proof that an individual program you're interested in halts, or you find a proof that it doesn't. But that's impossible because this is not a computable function.
So Turing's insight in 1936 is that incompleteness, that Gödel found in 1931, for any formal axiomatic theory, comes from a deeper phenomenon, which is uncomputability. Incompleteness is an immediate corollary of uncomputability, a concept which does not appear in Gödel's 1931 paper.
But Turing's paper has both good and bad aspects. There's a negative aspect of his 1936 paper, which I've just told you about, but there's also a positive aspect. You get another proof, a deeper proof of incompleteness, but you also get a kind of completeness. You find a perfect language.
There is no perfect language for mathematical reasoning. Gödel showed that in 1931, and Turing showed it again in 1936. But what Turing also showed in 1936 is that there are perfect languages, not for mathematical reasoning, but for computation, for specifying algorithms.
What Turing discovers in 1936 is that there's a kind of completeness called universality and that there are universal Turing machines and universal programming languages.
So on the one hand, Turing shows us in a deeper way that any language for mathematical reasoning has to be incomplete, but on the other hand, he shows us that languages for computation can be universal, which is just another name, a synonym, for completeness.
There are perfect languages for computation, for writing algorithms, even though there aren't any perfect languages for mathematical reasoning. This is the positive side, this is the completeness side, of Turing's 1936 paper.
Now, what I've spent most of my professional life on, is a subject I call algorithmic information theory
This is a place in pure mathematics where there's no structure. If you want to know the bits of the numerical value of the halting probability, this is a well-defined mathematical question, and in the world of mathematics all truths are necessary truths, but these look like accidental, contingent truths. They look random, they have irreducible complexity.
This is a maximal case of uncomputability, this is a place in pure mathematics where there's absolutely no structure at all. Although it is true that you can in a few cases actually know some of the first bits...
There are actually an infinite number of halting probabilities depending on your choice of programming language. After you choose a language, then you ask what is the probability that a program generated by coin tossing will eventually halt. And that gives you a different halting probability. The numerical value will be different; the paradoxical properties are the same.
Okay, there are cases for which you can get a few of the first bits. For example, if Ω starts with 1s in binary or 9s in decimal, you can know those bits or digits, if Ω is .11111... base two or .99999... base ten. So you can get a finite number of bits, perhaps, of the numerical value, but if you have an N-bit formal axiomatic theory, then you can't get more than N bits of Ω. That's sort of the general result. It's irreducible logically and computationally. It's irreducible mathematical information. It's a perfect simulation in pure math, where all truths are necessary, of contingent, accidental, maximal entropy truths.
So that's the bad news from AIT. But just like in Turing's 1936 work, there is a positive side. On the one hand we have maximal uncomputability, maximal entropy, total lack of structure, of any redundancy, in an information-theoretic sense, but there's also good news.
AIT, the theory of program-size complexity, the theory where Ω is the crown jewel, goes further than Turing, and picks out from Turing's universal Turing machines, from Turing's universal languages, maximally expressive programming languages. Because those are the ones that you have to use to develop this theory where you get to Ω.
AIT has the notion of a maximally expressive programming language in which programs are maximally compact, and deals with a very basic complexity concept which is the size of the smallest program to calculate something:
Now let me tell you, this definition of complexity is a dry, technical way of expressing this idea in modern terms. But let me put this into Medieval terminology, which is much more colorful. The notion of program-size complexity --- which by the way has many different names: algorithmic complexity, Kolmogorov complexity, algorithmic information content --- in Medieval terms, what we're asking is, how many yes/no decisions did God have to make to create something?, which is obviously a rather basic question to ask. That is, if you consider that God is calculating the universe.
I'm giving you a Medieval perspective on these modern developments. Theology is the fundamental physics, it's the theoretical physics of the Middle Ages.
I have a lot of time left --- I've been racing through this material --- so maybe I should explain in more detail how AIT contributes to the quest for the perfect language.
The notion of universal Turing machine that is used in AIT is Turing's very basic idea of a flexible machine. It's flexible hardware, which we call software. In a way, Turing in 1936 creates the computer industry and computer technology. That's a tremendous benefit of a paper that mathematically sounds at first rather negative, since it talks about things that cannot be calculated, that cannot be proved. But on the other hand there's a very positive aspect --- I stated it in theoretical terms --- which is that programming languages can be complete, can be universal, even though formal axiomatic theories cannot be complete.
Okay, so you get this technology, there's this notion of a flexible machine, this notion of software, which emerges in this paper. Von Neumann, the same von Neumann who invented the von Neumann integers, credited all of this to Turing. At least Turing is responsible for the concept; the hardware implementation is another matter.
Now, AIT, where you talk about program-size complexity, the size of the smallest program, how many yes/no decisions God has to make to calculate something, to create something, picks out a particular class of universal Turing machines U.
What are the universal computers U like that you use to define program-size complexity and talk about Ω? Well, a universal computer U has the property that for any other computer C and its program p, your universal computer U will calculate the same result if you give it the original program p for C concatenated to a prefix πC which depends only on the computer C that you want to simulate. πC tells U which computer to simulate. In symbols,
In other words, πC p is the concatenation of two pieces of information. It's a binary string. You take the original program p, which is also a binary string, and in front of it you put a prefix that tells you which computer to simulate.
Which means that these programs πC p for U are only a fixed number of bits larger than the programs p for any individual machine C.
These U are the universal Turing machines that you use in AIT. These are the most expressive languages. These are the languages with maximal expressive power. These are the languages in which programs are as concise as possible. This is how you define program-size complexity. God will naturally use the most perfect, most powerful programming languages, when he creates the world, to build everything.
I should point out that Turing's original universality concept was not careful about counting bits; it didn't really care about the size of programs. All a universal machine U had to do was to be able to simulate any other machine C, but one did not study the size of the program for U as a function of the size of the program for C. Here we are careful not to waste bits.
AIT is concerned with particularly efficient ways for U to be universal. The original notion of universality in Turing was not this demanding.
The fact that you can just add a fixed number of bits to a program for C to get one for U is not completely trivial. Let me tell you why.
After you put πC and p together, you have to know where the prefix ends and the program that is being simulated begins. There are many ways to do this.
A very simple way to make the prefix πC self-delimiting is to have it be a sequence of 0's followed by a 1:
The prefix πC is actually an interpreter for the programming language C. AIT's universal languages U have the property that you give U an interpreter plus the program p in this other language C, and U will run the interpreter to see what p does.
If you think of this interpreter πC as an arbitrary string of bits, one way to make it self-delimiting is to just double all the bits. 0 goes to 00, 1 goes to 11, and you put a pair of unequal bits 01 as punctuation at the end:
And there are more efficient ways to make the prefix self-delimiting. For example, you can put the size of the prefix in front of the prefix. But it's sort of like Russian dolls, because if you put the size |πC| of πC in front of πC, |πC| also has to be self-delimiting:
Let me compare the 1960s version of AIT and the 1970s version of AIT. Let me compare these two different theories of program-size complexity.
In the 1960s version, an N-bit string will in general need an N-bit program, if it's irreducible, and most strings are algorithmically irreducible. Most N-bit strings need an N-bit program. These are the irreducible strings, the ones that have no pattern, no structure. Most N-bit strings need an N-bit program, because there aren't enough smaller programs.
But in the 1970s version of AIT, you go from N bits to N+log2N bits, because you want to make the programs self-delimiting. An N-bit string will usually need an N+log2N bit program:
The 1970s version of AIT, which takes the idea of being self-delimiting from the prefix and applies it to the whole program, gives us even better perfect languages. AIT evolved in two stages. First we concentrate on those U with
And you can't even define the halting probability Ω in AIT1960. If you allow all N-bit strings to be programs, then you cannot define the halting probability in a natural way, because the sum for defining the probability that a program will halt
I want the halting probability to be finite. The normal way of thinking about programs is that there are 2N N-bit programs, and the natural way of defining the halting probability is that every N-bit program that halts contributes 1/2N to the halting probability. The only problem is that for any fixed size N there are roughly order of 2N programs that halt, so if you sum over all possible sizes, you get infinity, which is no good.
In order to get the halting probability to be between zero and one
This implies that no extension of a valid program is a valid program, and that the set of valid programs is what's called a prefix-free set. Then the fact that the sum that defines Ω must be between zero and one, is just a special case of what's called the Kraft inequality in Shannon information theory.
But this technical machinery isn't necessary. That 0 < Ω < 1 follows immediately from the fact that as you read the program bit by bit you are forced to decide where to stop without seeing any special punctuation. In other words, in AIT1960 we were actually using a three-symbol alphabet for programs: 0, 1 and blank. The blank told us where a program ends. But that's a symbol that you're wasting, because you use it very little. As you all know, if you have a three-symbol alphabet, then the right way to use it is to use each symbol roughly one-third of the time.
So if you really use only 0s and 1s, then you have to force the Turing machine to decide by itself where the program ends. You don't put a blank at the end to indicate that.
So programs go from N bits in size to N+log2N bits, because you've got to indicate in each program how big it is. On the other hand, you can just take subroutines and concatenate them to make a bigger program, so program-size complexity becomes sub-additive. You run the universal machine U to calculate the first object x, and then you run it again to calculate the second object y, and then you've got x and y, and so
These self-delimiting binary languages are the ones that the study of program-size complexity has led us to discriminate as the ideal languages, the most perfect languages. We got to them in two stages, AIT1960 and AIT1970. These are languages for computation, for expressing algorithms, not for mathematical reasoning. They are universal programming languages that are maximally expressive, maximally concise. We already knew how to do that in the 1960s, but in the 1970s we realized that programs should be self-delimiting, which made it possible to define the halting probability Ω.
Okay, so that's the story, and now maybe I should summarize all of this, this saga of the quest for the perfect language. As I said, the search for the perfect language has some negative conclusions and some positive conclusions.
Hilbert wanted to find a perfect language giving all of mathematical truth, all mathematical knowledge, he wanted a formal axiomatic theory for all of mathematics. This was supposed to be a Theory of Everything for the world of pure math. And this cannot succeed, because we know that every formal axiomatic theory is incomplete, as shown by Gödel, by Turing, and by my halting probability Ω. Instead of finding a perfect language, a perfect formal axiomatic theory, we found incompleteness, uncomputability, and even algorithmic irreducibility and algorithmic randomness.
So that's the negative side of this story, which is fascinating from an epistemological point of view, because we found limits to what we can know, we found limits of formal reasoning.
Now interestingly enough, the mathematical community couldn't care less. They still want absolute truth! They still believe in absolute truth, and that mathematics gives absolute truth. And if you want a proof of this, just go to the December 2008 issue of the Notices of the American Mathematical Society. That's a special issue of the Notices devoted to formal proof.
The technology has been developed to the point where they can run real mathematics, real proofs, through proof-checkers, and get them checked. A mathematician writes the proof out in a formal language, and fills in the missing steps and makes corrections until the proof-checker can understand the whole thing and verify that it is correct. And these proof-checkers are getting smarter and smarter, so that more and more of the details can be left out. As the technology improves, the job of formalizing a proof becomes easier and easier.
The formal-proof extremists are saying that in the future all mathematics will have to be written out formally and verified by proof-checkers.
The engineering has been worked out to the point that you can formally prove real mathematical results and run them through proof-checkers for verification. For example, this has been done with the proof of the four-color conjecture. It was written out as a formal proof that was run through a proof-checker.
And the position of these extremists is that in the future all mathematics will have to be written out in a formal language, and you will have to get it checked before submitting a paper to a human referee, who will then only have to decide if the proof is worth publishing, not whether the proof is correct. And they want a repository of all mathematical knowledge, which would be a database of checked formal proofs of theorems.
This is a substantial community, and to learn more, go to the December 2008 AMS Notices, which is available on the web for free in the AMS website. This is being worked on by a sizeable community, and the Notices devoted a special issue to it, which means that mathematicians still believe in absolute truth.
I'm not disparaging this extremely interesting work, but I am saying that there's a wonderful intellectual tension between it and the incompleteness results that I've discussed in this talk. There's a wonderful intellectual tension between incompleteness and the fact that people still believe in formal proof and absolute truth. People still want to go ahead and carry out Hilbert's program and actually formalize everything, just as if Gödel and Turing had never happened!
I think this is an extremely interesting and, at least for me, a quite unexpected development.
These were the negative conclusions from this saga. Now I want to wrap this talk up by summarizing the positive conclusions.
There are perfect languages, for computing, not for reasoning. They're computer programming languages. And we have universal Turing machines and universal programming languages, and although languages for reasoning cannot be complete, these universal programming languages are complete. Furthermore, AIT has picked out the most expressive programming languages, the ones that are particularly good to use for a theory of program-size complexity.
So there is a substantial practical spinoff. Furthermore, since I've worked most of my professional career on AIT, I view AIT as a substantial contribution to the search for the perfect language, because it gives us a measure of expressive power, and of conceptual complexity and the complexity of ideas. Remember, I said that from the perspective of the Middle Ages, that's how many yes/no decisions God had to make to create something, which obviously He will do in an optimum manner.
[Note that program-size complexity = size of smallest name for something.]
From the theoretical side, however, this quest was disappointing due to Gödel incompleteness and because there is no Theory of Everything for pure math. Provably there is no TOE for pure math. In fact, if you look at the bits of the halting probability Ω, they show that pure mathematics contains infinite irreducible complexity, and in this precise sense is more like biology, the domain of the complex, than like theoretical physics, where there is still hope of finding a simple, elegant TOE.
[Incompleteness can be considered good rather than bad: It shows that mathematics is creative, not mechanical.]
So this is the negative side of the story, unless you're a biologist. The positive side is we get this marvelous programming technology. So this dream, the search for the perfect language and for absolute knowledge, ended in the bowels of a computer, it ended in a Golem.
In fact, let me end with a Medieval perspective on this. How would all this look to someone from the Middle Ages? This quest, the search for the perfect language, was an attempt to obtain magical, God-like powers.
Let's bring someone from the 1200s here and show them a notebook computer. You have this dead machine, it's a machine, it's a physical object, and when you put software into it, all of a sudden it comes to life!
So from the perspective of the Middle Ages, I would say that the perfect languages that we've found have given us some magical, God-like powers, which is that we can breath life into some inanimate matter. Observe that hardware is analogous to the body, and software is analogous to the soul, and when you put software into a computer, this inanimate object comes to life and creates virtual worlds.
So from the perspective of somebody from the year 1200, the search for the perfect language has been successful and has given us some magical, God-like abilities, except that we take them entirely for granted.
Thanks very much!
[Twenty minutes of questions and discussion followed. These have not been transcribed, but are available via digital streaming video at http://pirsa.org/09090007/.]
[17 Nov 2009]