On Wednesday, November 13, 2002, at 09:12 AM, Tyler Durden wrote:
"All religions are complete systems. Some people consider them useful,
but I'm not sure it classifies as "the real world".
:-)"
I've wondered about that...I suspect that if God exists, then He is true but unprovable in any useful system!
-TD
PS: According to Godel's biographer, Godel at one point passed around a proof of the existence of God! (But towards the end of his life he also started wearing a surgical mask everywhere and became intensely germaphobic...)
There are a lot of Godel anecdotes to tell. I never met him.
Two things about his theory:
1. There's a more powerful (IMNSHO) formulation of it in terms of algorithmic information theory, usually associated with Greg Chaitin but also drawing on the AIT work of Kolmogorov and others. This says, in informal language, "no theory can describe something more complicated than itself." If a theory has 20 bits of complexity, things of 21 bits or more just can't be "described/proved." Rudy Rucker has a good description of this in his excellent book "Mind Tools." And Chaitin has authored several books and a few very readable "Scientific American" types of articles. Google will have more on his sites, his papers.
2. This said, my point about not looking to Godelian undecidability sorts of issues for crypto is that it just appears to be "too far out there." Nobody, to my knowledge, has ever found a way to make such things useful in crypto...not even things like "Presburger arithmetic," which is "harder" than NP-complete but not yet Godelian undecideable.
(One semi-joke is that Godel's results are something every mathematician should learn about but that no working mathematician will ever actually need to use.)
--Tim May
