In this article, Scott Aaronson talks about using Turing Machines for proving the Rosser Theorem.
What is the relationship between the numbering that Gödel used in his proof of incompleteness and Turing Machines?
$\begingroup$
$\endgroup$
2
-
$\begingroup$ You might want to read this MO post. $\endgroup$– BurakCommented Dec 30, 2015 at 13:39
-
$\begingroup$ Turing machines can be numbered according to their representation for a Universal Turing Machine. $\endgroup$– Thorbjørn Ravn AndersenCommented Dec 30, 2015 at 21:33
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
13
It's simple. If the halting problem is undecidable, then PA is not complete, since otherwise, you could solve the halting problem by searching for proofs in PA. And the same argument works for any sound computably axiomatizable theory $T$ able to express arithmetic. Given a Turing machine $M$ on input $i$, you formulate the assertion $\sigma$ asserting that $M$ halts on $i$, and then search for a proof in $T$ of $\sigma$ or a proof of $\neg\sigma$. If your theory were complete, then you'll find one or the other, and this would solve the halting problem. Since the halting problem is not solvable, there must be sentences of this form that are not settled by the theory.
This argument proves the first incompleteness theorem as an elementary consequence of the halting problem. The second incompleteness theorem takes a bit more work.
There is more discussion on Are the two meanings of undecidability related? and How undecidable is the spectral gap problem?
answered Dec 30, 2015 at 13:45
-
$\begingroup$ Goes also the other way. If halting problem would be decidable you could make PA complete. $\endgroup$– Lucas K.Commented Dec 30, 2015 at 19:22
-
$\begingroup$ I agree with that statement; but perhaps it would paint a somewhat fuller picture to say that the completions of PA are branches through a certain computable tree. It follows that there are completions that are low, and these have strictly lower complexity in the Turing degrees than the halting problem. Meanwhile, other completions are far more complicated than the halting problem. $\endgroup$ Commented Dec 30, 2015 at 19:32
-
$\begingroup$ For example, true arithmetic is a completion of PA with Turing complexity $0^{(\omega)}$. $\endgroup$ Commented Dec 30, 2015 at 20:49
-
1$\begingroup$ @JoelDavidHamkins Another point, you say "the same argument works for any sound computably axiomatizable theory $T$". I'm probably mistaken, but doesn't the incompleteness theorem only assume consistency (and not soundness)? If so, is it viable to prove undecidability of the halting problem implies incompleteness of T, assuming that $T$ is only consistent? I suppose the linked blog post does this when it is proving Rosser's strengthened version of the incompleteness theorem? $\endgroup$– gowrathCommented Jun 17, 2017 at 3:54
-
1$\begingroup$ @gowrath Thinking about the converse is an interesting idea. I don't know any direct argument for proving that the incompleteness of PA implies the halting problem is undecidable. And given that Turing's proof of the undecidability of the halting problem is so quick, it would be hard to improve upon it. About soundness, the proof of incompletenes via the halting problem seems to use it, since one needs the veracity of the proof. But I suppose that you can eliminate this by re-proving the undecidability of the halting problem in T, thereby effectively making T sound enough for the purpose. $\endgroup$ Commented Jun 17, 2017 at 11:25