Wednesday, August 23, 2006

Incompleteness and room for growth

Recently I read an exposition on Godel's proof of incompleteness. There the authors Ernest Nagel and James R. Newman do a very nice job of explaining not only the proof but also triggering philosophical insights without loosing the details. The two main results of Godel's seminal paper are: any logical system capable of supporting Peano's axioms (simply stated a system supporting the well-evolved axioms and deducing abilities of humans)
  • could not be both consistent and complete

  • could not prove itself consistent without proving itself inconsistent
So why is the result so astounding or profound? One of the main reasons is that he proved (to be clear he used no meta reasoning) to show what great minds (like that of David Hilbert, Jules Richard) have been conjecturing about limits of human ability of mental conception. This result has many practical applications similar to those of the result by Cook's result on complexity of theorem proving procedures (the seminal paper in complexity theory). They both gave us reasoning ability to direct research efforts in their respective fields viz. logic and computational complexity (and algorithm design). There are results in almost all fields having similar effects (like result of Nash in game theory, result of Einstein in atomic physics).

If a system cannot be complete and consistent what reasoning can we take help of, to design and implement a system that is useful. No need to worry! We have pearls in pile of human-knowledge-jewelry known as probability theory, theory of statistics at our disposal. These theories for example helped building randomized algorithms, learning theory which unquestionably have proven to be useful.

The research directions consequent to any negative result like incompleteness theorem are essentially examples of positive thinking. The incompleteness theorem implies conjectures which intuitively are true but hard to be proven are always possible thus ineffect guaranteeing room for growth or increased depth of understanding. Look out for the recent exuberance over the potentially complete proof of Poincare's conjecture by Grisha Perelman who purportedly denied the Fields medal.

No comments: