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?
MathOverflow is a question and answer site for professional mathematicians. It only takes a minute to sign up.
Sign up to join this communityIn 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?
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?