Live data from Hacker News

What Do Gödel's Incompleteness Theorems Mean?

quantamagazine.org

71–72 of 72 posts

Re: What Do Gödel's Incompleteness Theorems Mean?

#71
post #3

Earlier quoted context omitted.

That part you quoted was interesting to me too. I remember once re-reading the incompleteness theorems - where it talks about a "finite set of axioms", it seemed there may be a loophole if we can imagine a theoretically infinite set of axioms, as a way to approach completeness. Overall I really enjoyed this article, short interviews with mathematicians and philosophers on a topic I've often thought about.

Some people, when confronted with a Gödel's Incompleteness Theorems, think "I know, I’ll use a theoretically infinite set of axioms." Now they have aleph-nought problems.

"..How about infinity plus one! Or infinite infinities!" -- Every child who learns about infinity for the first time, but also serious mathematicians in philosophical struggle with the truth. And Cantor, may the angels soothe his troubled soul.

Re: What Do Gödel's Incompleteness Theorems Mean?

#72

Earlier quoted context omitted.

> Gödel completeness theorem is the really big deal. Except it isn't. That computer program turns out to be one of those wretched tree search ones that soon bogs down. The real problem turns out to be the combinatorial explosion inherent in unstructured search through the Herbrand universe. Yup. Incompleteness is sort of a red herring. P≠NP (even though unproven) yields the real, practical, painful incompleteness.

P versus NP could be a red herring too. If P=NP, but the best asymptotic solution is n^7, and it has so much overhead that the best practical solution is n^9, then it doesn't really matter that it isn't exponential. It's still unsolvable for easily accessible problem sizes.

You think 7 and 9 are fun, imagine the number is instead astronomically big as in BB(8).
Post reply on HN