Lambda the Ultimate

Apropos of the recent discussion on the relationship between software and mathematics, it seemed the right moment to introduce a curious piece from a curious and entertaining spirit named Gregory J. Chaitin. If you've never read his work before, it's a treat. I thought about posting it to the LtU fun house, but hey, the man's serious, too, you know! Gets a paycheck from IBM! And uses Lisp! And talks about Turing completeness! The gist of Chaitin's work is that abstract mathematics as we know it turns out to be a much more "ad hoc" or "pragmatic" endeavor than is commonly known, in his view. Recursive function theory is prominent.

Okay, so why is all this interesting? Well, some of you may know already, but let me wave my hands frantically in the last few minutes and say why....This looks like a kind of programming madness, right? ... Yes, programming can be an obsession, it can ruin your life. You can sit at your terminal watching your life fall apart as you stay there hacking away until 4 in the morning! But is there any other justification for this except as a kind of drug? Well, I think so! I think this has some philosophical significance.

What's the point about this incompleteness theorem, about this technical result? ... [W]hat this incompleteness result shows you is that ... essentially the only way to prove what a bit of Omega is, is to add the theorem that you want to prove as a new axiom. It's irreducible mathematical information. Now you can prove anything by adding it as a new axiom. The point here is that for Omega that's essentially the only way to do it. No compression is possible. So there is no structure, there is no pattern, Omega has maximum entropy, it mirrors independent tosses of a fair coin. Now to a physicist what I'm saying sounds pretty reasonable, right? Omega has maximum entropy, the bits of Omega are completely uncorrelated. But to a mathematician this all sounds weird!

My new Omega is a particular well-defined real number. It's a real number with a rather simple definition, I can even write the LISP program that defines Omega on one computer screen. So you believe, thinking in Platonic terms, that each bit is either a 0 or a 1, even if I'm never going to know which. But it's black or white, right? And what I'm saying is that I think that it's really better to think that it's grey. It's really better to think that each bit of Omega has probability one-half of being 0 or of being 1—even though it's a particular well-determined bit, because I've written out the program that defines this number.