Incomplete

I've been pondering for some time as to whether I should write about "this" or not. Today concluded I should do it anyway.

If you are reading this post, I'd like to suggest that though it might get a tad confusing for a moment, but read it fully ... If you understand this one, then ...; you'll see ... Just read on.


The "this" I was referring to is something called the incompleteness theorem.

Kurt Gödel, in his famous paper "On Formally Undecidable Propositions" proved this celebrated and oft misunderstood theorem.

Consider this:

1. Someone introduces Gödel to a UTM, a machine that is supposed to be a Universal Truth Machine, capable of correctly answering any question at all.
   
   
2. Gödel asks for the program and the circuit design of the UTM. The program may be complicated, but it can only be finitely long. Call the program P(UTM) for Program of the Universal Truth Machine.
   (If the concept of a computer program or a circuit seem alien terms just think of P(UTM) as a (formal) description of the UTM and its workings in words or symbols)
   
   
3. Smiling a little, Gödel writes out the following sentence: "The machine constructed on the basis of the program P(UTM) will never say that this sentence is true." Call this sentence G for Gödel. Note that G is equivalent to: "UTM will never say G is true."
   
   
4. Now Gödel laughs his high laugh and asks UTM whether G is true or not.
   
   
5. If UTM says G is true, then "UTM will never say G is true" is false. If "UTM will never say G is true" is false, then G is false (since G = "UTM will never say G is true"). So if UTM says G is true, then G is in fact false, and UTM has made a false statement. So UTM will never say that G is true, since UTM makes only true statements.
   
   
6. We have established that UTM will never say G is true. So "UTM will never say G is true" is in fact a true statement. So G is true (since G = "UTM will never say G is true").
   
   
7. "I know a truth that UTM can never utter," Gödel says. "I know that G is true. UTM is not truly universal."
   

The logic in the embodied in the above lines is simple. But the more you think about it, the more it grows on you. Stated very very loosely the theorem implies (The prof. who taught me the formal logic course would probably flip if he saw this one):


All logical systems of any complexity are, by definition, incomplete; each of them contains, at any given time, more true statements than it can possibly prove according to its own defining set of rules.



Although this theorem can be stated and proved in a rigorously mathematical way, what it seems to say is that rational thought can never penetrate to the final ultimate truth. But, paradoxically, to understand Gödel's proof is to find a sort of liberation.

The metaphorical analogue to Gödel's Theorem suggests that ultimately, we cannot understand our own mind/brains ... Just as we cannot see our faces with our own eyes, is it not inconceivable to expect that we cannot mirror our complete mental structures in the symbols which
carry them out?

Gödel's Theorem has been used to argue that a computer can never be as smart as a human being because the extent of its knowledge is limited by a fixed set of axioms, whereas people can discover unexpected truths.

Fantastic, is it not ? I stumbled across this theorem about a year back when doing a course called the Theory of Computation. It is a masterpiece of formal logic. Imagine the fields of study and thought it cuts across.

For those whose curiosity I piqued by this post I suggest you read this fascinating, Pulitzer prize-winning book by Douglas Hofstadter "Gödel, Escher, Bach: an Eternal Golden Braid". You'll find that mathematics, art and music are not so different from each other. They are all reflections of the most beautiful of nature's creation: the human mind. Hofstadter explains the book is about "the word I. Consciousness. It was about how thinking emerges from well-hidden mechanisms, way down, that we hardly understand."


Sources I used to research this article:

• Gödel's Incompleteness Theorem
  
• Wikipedia Entry on the Incompleteness Theorem