Prove Gödel's incompleteness theorem using halting problem

A somewhat subtle point in the proof that Zhen Lin sketched in another answer is that it has to assume that Peano arithmetic is $\omega$-consistent. This is because the algorithm sketched looks for a proof of "there exists a number of steps after which $M$ halts", but if Peano arithmetic was not $\omega$-consistent then it might prove a statement of that kind without such a number actually existing. This extra assumption of $\omega$-consistency is typical of computability-theoretic proofs of the incompleteness theorem.

I don't know of any proof of the full incompleteness theorem (the one that assumes only consistency) just from the unsolvability of the halting problem, and I doubt such a proof exists for two reasons.

First, the unsolvability of the halting problem is a fact at the meta level (a fact about the standard model). If you look at some theory of arithmetic that is consistent but not satisfied by the standard model, it could prove all sorts of false statements about whether various Turing machines halt. The assumption of $\omega$-consistency is exactly intended to give a link between the meta level and the object level of the theory at hand. Without such an assumption, the two can be very different.

Second, there are (non-effective) completions of Peano arithmetic that do not solve the halting problem, and are of strictly lower Turing degree while still being uncomputable. In other words, formally, the Medvedev degree of the set of completions of PA is strictly weaker than the Medvedev degree of the set of oracles that compute the Halting problem. My interpretation of this result is that it's a steep obstacle to proving the full incompleteness theorem using just computability-theoretic methods, because it means we can't just reduce the completion problem to the halting problem as is normally done in computability.

Part 2

Now I want to write about the blog post that you can find here which was linked in the comments. The method in that post uses a different unsolvable problem, namely the problem of finding a separating set for a certain pair of recursively inseparable r.e. sets. These sets are the set of machines which PA can prove to halt, and the set of machines which PA can prove to not halt. In the blog post, this separating set is a solution to the "Consistent Guessing Problem".

The Turing degrees that are able to compute such sets are known as PA degrees (Wikipedia article) because they are also the degrees that are able to compute a completion of Peano arithmetic. There is a little more info on these degrees in the Wikipedia article.

We will assume Peano Arithmetic is consistent throughout. Suppose Gödel's first incompleteness theorem is false; that is, assume for every well-formed sentence $P$ in the language of Peano Arithmetic, either $P$ is provable or $\lnot P$ is provable. Then we may solve the halting problem: consider a Turing machine which accepts an encoded Turing machine $M$ as input, forms the sentence $P$ in Peano Arithmetic which asserts that $M$ halts on all inputs, and searches for a proof of $P$ or $\lnot P$ by iterating through all possible proofs, halting when such a proof is found. This Turing machine is guaranteed to halt by our assumption, so we have indeed solved the halting problem. But the halting problem cannot be solved, so Gödel's first incompleteness theorem must be true.

Note: Carl Mummert's answer elaborates on the consistency assumption required here.

Here is a reference http://www.logicmatters.net/resources/pdfs/PartIII.pdf discussing both methods (Gödels method and the proof using the halting problem)

Scott Aaronson made a wonderful post about this (and an even stronger result) on his blog: http://www.scottaaronson.com/blog/?p=710