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

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?

• You might want to read this MO post. – Burak Dec 30 '15 at 13:39
• Turing machines can be numbered according to their representation for a Universal Turing Machine. – Thorbjørn Ravn Andersen Dec 30 '15 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)}$. – Joel David Hamkins Dec 30 '15 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? – gowrath Jun 17 '17 at 3:54