www.cs.umaine.edu/~chaitin/cmu.html
Complexity magazine on Limits in Mathematics and Physics'' (Vol. We're in a state of euphoria now in the computer business because things are going so well: the web, e-commerce. It's all paying for our salaries, and it's a nice moment to be around, when things are going so well. But I'd like to make the outrageous claim, that has a little bit of truth, that actually all of this that's happening now with the computer taking over the world, the digitalization of our society, of information in human society, you could say in a way is the result of a philosophical question that was raised by David Hilbert at the beginning of the century. It's not a complete lie to say that Turing invented the computer in order to shed light on a philosophical question about the foundations of mathematics that was asked by Hilbert. And in a funny way that led to the creation of the computer business. It's not completely true, but there is some truth in it. You know, most historical statements are a lie, so this one isn't that much worse than most others! So I'd like to explain the philosophical history of the computer. In a way what happened, and I'll tell you more, is that Hilbert said we should formalize all of mathematics, mathematical reasoning. And this failed: it took Gdel and Turing to show that it couldn't be done. But in fact it succeeded magnificently, not formalization of reasoning, but formalization of algorithms has been the great technological success of our time --- computer programming languages! So if you look back at the history of the beginning of this century you'll see papers by logicians studying the foundations of mathematics in which they had programming languages. Now you look back and you say this is clearly a programming language! If you look at Turing's paper of course there's a machine language. If you look at papers by Alonzo Church you see the lambda calculus, which is a functional programming language. If you look at Gdel's original paper you see what to me looks like LISP, it's very close to LISP, the paper begs to be rewritten in LISP! So I'd like to give you this hidden philosophical history of computer technology which is how philosophically minded mathematicians set out to solve once and for all the foundational problems of mathematics and did not succeed but helped to create computer technology as a by product. We're all benefiting from the glorious failure of this project! And what I'd like to do is to tell you that in fact I've done some more work in this area. What Gdel and Turing showed is that axiomatic formal reasoning has certain limitations. And at first people were tremendously shocked and then they shrugged and said, so what? And my misfortune or fortune was that I didn't want to shrug. And I'm going to tell you the story of my attempt to understand Gdel incompleteness. So let me start at the beginning and tell you this story of a hundred years of intense worry, crisis, self-doubt, self-examination and angst about the philosophy of mathematics. There've been lots of crises in the history of mathematics. One of the first crises was the Pythagorean result that the square root of two is irrational. And the fact that this was a crisis survives in the word irrational''. Remember the Greeks thought that rationality was the supreme goal --- Plato! If a number is called irrational that means that this was the Gdel incompleteness theorem of ancient Greece. A lot of people said this is nonsense, we're talking about infinitesimals, what is this? Bishop Berkeley was a theologian and he said, pure mathematicians make as little sense as theologians, you can't reject us saying we're unreasonable. The way you deal with evanescent quantities in the calculus --- this was before the calculus had a rigorous foundation --- is as bad as our theological discussions! Then there was a crisis about the parallel postulate, about non-Euclidean geometries. But the particular crisis that I want to tell you about goes back a little more than a hundred years to work of Cantor on set theory. Cantor: Theory of Infinite Sets So my talk is very impractical. We all know that you can have a start-up and in one year make a million dollars if you're lucky with the web. So this is about how not to make any money with the web. This is about how to ruin your career by thinking about philosophy instead. So Cantor was obsessed with the notion of infinite, and it's not mentioned that he was obsessed with infinite because he was interested in theology and God, which is edited out from the accounts now, but that was the original idea. This is going to be the first number after all the finite numbers. This sequence goes on forever, but let's put something after all of those. Instead of getting high on alcohol or grass you get high on ideas like this. After a while you don't know where you're standing or what's going on! This number is the smallest solution of the equation x = w^x And it's called e 0 , epsilon nought, I don't know why. Because you start having problems with how to name things, because up to here I was using normal algebraic notation just throwing in w. I don't know whether it's mathematics, but it's very imaginative, it's very pretty, and actually there was a lot of practical spin-off for pure mathematicians from what Cantor was doing. Poincar, the great French mathematician, said set theory is a disease, he said, from which I hope future generations will recover. But other people redid all of mathematics using the set-theoretic approach. So modern topology and a lot of abstract mathematics of the twentieth century is a result of this more abstract set-theoretic approach, which generalized questions. The mathematics of the nineteenth century was at a lower level in some ways, more involved with special cases and formulas. The mathematics of the twentieth century --- it's hard to write a history of mathematics from the year ten-thousand looking back because we're right here --- but the mathematics of the twentieth century you could almost say is set-theoretical, structural'' would be a way to describe it. The mathematics of the nineteenth century was concerned with formulas, infinite Taylor series perhaps. But the mathematics of the twentieth century went on to a set-theoretic level of abstraction. And in part that's due to Cantor, and some people hate it saying that Cantor wrecked and ruined mathematics by taking it from being concrete and making it wishy-washy, for example, from hard analysis to abstract analysis. It was very controversial, and what didn't help is in fact that there were some contradictions. There were some cases in which you got into really bad trouble, you got obvious nonsense out. And the place you get obvious nonsense out in fact is a theorem of Cantor's that says that for any infinite set there's a larger infinite set which is the set of all its subsets, which sounds pretty reasonable. This is Cantor's diagonal argument --- I don't have time to give you the details. So then the problem is that if you believe that for any infinite set there's a set that's even larger, what happens if you apply this to the universal set, the set of everything? The problem is that by definition the set of everything has everything, and this method supposedly would give you a larger set, which is the set of all subsets of everything. So there's got to be a problem, and the problem was noticed by Bertrand Russell. Bertrand Russell Cantor I think may have noticed it, but Bertrand Russell went around telling everyone about it, giving the bad news to everyone! The disaster that Russell noticed in this proof of Cantor's was the set of all sets that are not members of themselves, that turns out to be the key step in the proof. And the set of all sets that aren't members of themselves sounds like a reasonable way to define a set, but if you ask if it's inside itself or not, whatever you assume you get the opposite, it's a contradiction, it's like saying this statement is false. The set of all sets that are not members of themselves is contained in itself if and only if it's not contained in itself. So does this mean that some ways of defining se...
|