# What is the relationship between Turing Machines and Gödel's Incompleteness Theorem?

What is the relationship between the numbering that Gödel used in his proof of incompleteness and Turing Machines?

• You might want to read this MO post. Dec 30, 2015 at 13:39
• Turing machines can be numbered according to their representation for a Universal Turing Machine. Dec 30, 2015 at 21:33

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.
• For example, true arithmetic is a completion of PA with Turing complexity $0^{(\omega)}$. Dec 30, 2015 at 20:49
• @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? Jun 17, 2017 at 3:54