Wednesday, February 16, 2005

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:

11 comments:

  1. Christ I'm glad I quit studying logic formally way before I got to this. This I assure you is the kind of thing that would've made me take a Klashnikov to school :)

    But in some warped way I guess it makes me dizzy because I do understand the point. (Note: the Point, not the Process)

    ReplyDelete
  2. D Hof.. Amazing writer, especially when combined with the likes of Dennet. Don't know if you have picked up 'The Mind's I'.. Brilliant collection.

    Godel's works have a curious self-referencing sequence... your post may provoke something in my mind now. :) Danke!

    ReplyDelete
  3. @Morq - as you say logic cud hav induced you to violence - so u gave up logic and hence gave up being induced to violence by it - that is perfectly logical :-)) .


    @Neha - Didn't know I'd find a D Hof admirer so quick - glad to hav u on the blog. I have not read 'The Mind's I' completely. And I can't find the `Post a Comment' link on Within/Without - any reasons for not keeping one? I thought I was the most obscure poet who existed, till I read what you wrote ... teee hee hee :-) I guess and I feel one's poetry would make sense to the one and only the one, even if it was written for someone else ...

    ReplyDelete
  4. GGrr..
    From what I've heard, 'some' of my poetry does make sense to others! LOL

    D Hof is perhaps one of the few writers who dares to brave what is often considered slightly 'irrational' 'science'. One of my all time favourites is Fritjof Capra. One more writer I have grown to like is Jared Diamond...

    About not being able to post a comment, mostly because I got a lot of spam, and even more so, the comments got personal. Read http://nehasri_DOT_blogspot_DOT_com/2004/12/disclaimer.html to find out with what conditions commenting was once enabled, and ergo, why disabled. :)

    ReplyDelete
  5. @Rapunzel - a big thank you is in order - so - THANK YOU!

    @Neha - Ah yes ... The Tao of Physics. And I'll not ask about "calling you/meeting you/mailing you" and I'll not comment either (for obvious reasons .. lol). Hey I just realized - the biggest spammer on my blog's comment section - is probably me :-D.

    ReplyDelete
  6. k....then again...maybe i shouldnt be so prejudiced...maybe theorems do NOT really mean that i dont understand.yeah?ok...this time i shall actually read more than the fust few lines...

    ReplyDelete
  7. OMG!!!this IS beautiful!!!!!! and actually echoes somewhat... something i'd said in one of my posts abt faith and logic....wow!!am totally in awe!!

    ReplyDelete
  8. @Rapunzel: Glad u read it through, and liked it. *Feeling extremely pleased with myself*

    ReplyDelete