Saturday, December 12, 2009

Gödel's theorems -- transcending transcendence

It occurred to me that perhaps I should have preceded the previous post with this one, a discussion about the consequences of Gödel that would answer the question "so what?" So what if Principia Mathematica is never going to contain all of mathematical truth? What does that have to do with anything?

Gödel's Incompleteness Theorem exposes a glaring weakness in any formal system. It points at a strange disconnect between logic and truth. The beauty and austerity of formal logic become questionable -- we can't know everything there is to know about the world using formal, deductive, logical reasoning!

I guess this is old news. But personal experience suggests that it is still easy to fall for the misconception that deductive reasoning is somehow "better" than other types of reasoning. Yes, it is much cleaner, but heuristics, induction, abduction and analogical reasoning are so much more powerful, and play such an important role in intelligent behaviour.

Truth is Weird

Gödel's theorem shows that there are lots more subtleties in truth than we give it credit for. Perhaps the crux of Gödel's result come from our misunderstanding of what truth really mean in our world. I guess the other question is: what exactly do mathematical truths mean in our world? Especially strange results like the Banach-Tarski paradox, so called the paradoxical decomposition of spheres...

Argument against strong AI

J.R. Lucas argued using Gödel's Incompleteness Theorem that machines can never be as intelligent as human beings. He argued that since machines are inevitably formal systems, Gödel's Incompleteness Theorem applies. Thus, there must be some truth that machines ought not to be able to discover, but that humans can -- we can follow the construction from the last post to construct a statement that means "this theorem is not provable by the machine". While we know that this statement is true, the machine would never be able to prove or disprove it. Thus humans will always have the upper hand.

Although this is an appealing argument, consensus is that it doesn't quite work. Two of the possible arguments against Lucas are:
1. In order for Gödel's theorem to hold, we must assume that the formal system is consistent. Computers need not be to be a consistent formal system. (Humans are quite inconsistent as well.)
2. There are paradoxical sentences that humans cannot assign truth value to; thus perhaps we are formal systems that are more powerful, but not something that cannot be surmounted by computers.
A common theme

Themes that come up in Gödel's theorem and its proof are quite ubiquitous. The futility of the formal system in attempt to "break out" of its bound of incompleteness is like Escher's dragon, below, trying to break out of the 2-dimensionality of your screen.

There's a certain "zen"-ness to all this. Even the distinction between provability and unprovability is very much like the concept of the knowable versus the unknowable. The existence of an unprovable statement is akin to the proposition that there will always be unknowable truths. (Reminds me of this quote from Douglas Adams, the first one under "The Universe", for some strange reason)

The common theme here is, I believe, the desire to transcend, coupled with the inability to transcend. If right now, someone asked me to bet on what the meaning of life is, then I would put on my "pretend to be Zen" hat and answer: to transcend transcendence.

End of Entry