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:
Post a Comment