## Tuesday, January 12, 2010

### The Limits of Knowledge, Part I

One of the foundational questions of Computer Science is "what can be computed?" It's a vaguely philosophical question, but it turns out to be approachable from a mathematically rigorous direction as well. I think it's probably the most important thread in modern mathematics (1930's onwards modern...), with interesting implications for the universe and our position there-in (plus the story has a few good characters). And happily, it's one of those mathematical concepts that can be explained without resorting to the use of Greek lettering. It's not the future so much as the recent past, and it's not according to me, just retold, but it's one of those concepts I find interesting enough to want to share with the world again.

So what can be computed? The answer isn't "everything", although that's not immediately obvious. You could build a computer as large as our galaxy, and run it for a trillion years, and there are questions you wouldn't have a definite answer to. Not necessarily even very complex questions. Similiarly, mathematics purports to deal with hard truths and unquestionable proofs, but it turns our not every mathematical question you can think of has an answer you can prove.

But before looking towards the outer reaches, it's useful to look in towards the seeds of mathematics first. A mathematical proof starts with a proposition, then using valid mathematical rules derives that this statement is true or false. The valid mathematical rules are usually just proofs that somebody else already proved true. But those need to follow some set of rules as well. You can build a huge tower of mathematics, but it ultimately needs to rest on something, some ground statement. We call these axioms. Nobody proves axioms. We just say, "yes, that must be true!" and go from there. If A and B are true, then just A is true as well. Why? I don't know. It's what we understand 'and' to mean. It's one of the facts we just start with.

And it's the first limit of our knowledge.

Any mathematical system needs to start with a set of axioms. And because you can't prove these, you don't know for certain they're true. And perhaps more important, you don't know if you missed one. Perhaps there are huge classes of really interesting things you could learn about the universe, if you could just think of this other universal truth.

Or put another way, think of the game children play. "We've got to go." "Why?" "We're late." "Why?" "You took too long getting ready" "Why?" "You were distracted by your toys" "Why?..."

At some point you either need to find your way into a loop, or say "just because". So it is with Math. And so it is with anything. Once we thought the world was made of fire,water,earth and air. Then we broke those down into atoms. Now we think of quarks or strings, but ultimately we're always left with some fundamental bit of reality that's just there. You can reach a bottom, but you've always got to just accept it as true, and accept the fact that their could be another layer you can't see.

Thus as far as physics or religion progress, there's always going to be that nagging question of "is this it? Is there nothing more to reality?" No matter how far our understanding advances, there's always going to be at least one statement we'll just have to take on faith. And if the tower of math and science is on a slightly shaky foundation, the sky above it is just as uncertain. But that's another post...