In this [article](http://www.scottaaronson.com/blog/?p=710), 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? 



What is the relationship between Turing Machines and Gödel's Incompleteness Theorem?
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?](https://mathoverflow.net/a/130815/1946) and [How undecidable is the spectral gap problem?](https://mathoverflow.net/a/225946/1946)


