4 ms·

Isn't this an effective argument that ZFC's axioms are "not enough"?

roywiggins 8y ago
I'm pretty confident that no set of axioms could make every Turing machine's halting problem decidable. From the paper: "consider a Turing machine Z that enumerates, one after the other, each of the provable statements in ZFC. To describe how such a machine might be constructed, Z could iterate over the axioms and inference rules of ZFC, applying each in every possible way to each conclusion or pair of conclusions that had been reached so far. We might ask Z to halt if it ever reaches a contradiction; in other words, Z will halt if and only if it finds a proof of 0 = 1. Because this machine will enumerate every provable statement in ZFC, it will run forever if and only if ZFC is consistent. It follows that Z is a Turing machine for which the question of its behavior (whether or not it halts when run indefinitely) is equivalent to the consistency of ZFC. Therefore, just as ZFC cannot prove its own consistency (assuming ZFC is consistent), ZFC also cannot prove that Z will run forever." This argument works for every axiomatic system: there will be a Turing machine whose halting problem cannot be proved in it. If there wasn't, you'd be able to prove that the consistency-checking machine would halt, thereby proving that the system is consistent, which is impossible per Godel incompleteness.
- IngoBlechschmid 8y ago
  Indeed, precisely that is true. The shocking conclusion of Gödel's incompleteness theorem is that the problem that our logical foundations are incomplete is inherently unfixable; any extended system of axioms will have new statements which are true but which it cannot prove. (That said, there are certain sub-areas of mathematics where we can prove that every true result in one of these sub-areas is actually provable from a certain system of axioms adapted to the given sub-area. But there is no way around Gödel's incompleteness phenomenon if one wants to encompass all of mathematics (and even arithmetic with natural numbers suffices to yield the incompleteness phenomenon).)

I'm pretty confident that no set of axioms could make every Turing machine's halting problem decidable. From the paper: "consider a Turing machine Z that enumerates, one after the other, each of the provable statements in ZFC. To describe how such a machine might be constructed, Z could iterate over the axioms and inference rules of ZFC, applying each in every possible way to each conclusion or pair of conclusions that had been reached so far. We might ask Z to halt if it ever reaches a contradiction; in other words, Z will halt if and only if it finds a proof of 0 = 1. Because this machine will enumerate every provable statement in ZFC, it will run forever if and only if ZFC is consistent. It follows that Z is a Turing machine for which the question of its behavior (whether or not it halts when run indefinitely) is equivalent to the consistency of ZFC. Therefore, just as ZFC cannot prove its own consistency (assuming ZFC is consistent), ZFC also cannot prove that Z will run forever." This argument works for every axiomatic system: there will be a Turing machine whose halting problem cannot be proved in it. If there wasn't, you'd be able to prove that the consistency-checking machine would halt, thereby proving that the system is consistent, which is impossible per Godel incompleteness.

IngoBlechschmid 8y ago
Indeed, precisely that is true. The shocking conclusion of Gödel's incompleteness theorem is that the problem that our logical foundations are incomplete is inherently unfixable; any extended system of axioms will have new statements which are true but which it cannot prove. (That said, there are certain sub-areas of mathematics where we can prove that every true result in one of these sub-areas is actually provable from a certain system of axioms adapted to the given sub-area. But there is no way around Gödel's incompleteness phenomenon if one wants to encompass all of mathematics (and even arithmetic with natural numbers suffices to yield the incompleteness phenomenon).)