Is there a relationship between Turing's Halting theorem and Gödel Incompleteness Turing's proof that a Halting oracle is impossible and Gödel's proof that and omega-consistent first order theory of arithmetic must be incomplete are similar in that they use self-referential arguments. Is there an interesting relationship between them especially in light of the Curry-Howard Correspondence and especially the categorical version thereof i.e. the Curry-Howard-Lambek Correspondence.


Turing's proof that a Halting oracle is impossible and Gödel's proof that and omega-consistent first order theory of arithmetic must be incomplete are similar in that they use self-referential arguments. Is there an interesting relationship between them.

Well, Gödel's theorem is a simple consequence of Turing's proof.
Take a look at my Introduction to Gödel's Theorems, for example. §43.2 (in the numbering of the second edition) shows that the recursive unsolvability of the halting problem implies that the set of truths of the first-order language of arithmetic is not recursively enumerable. But the theorems in that language of a formalized theory $T$ are recursively enumerable. So there are truths that $T$ can't prove, and if $T$ is sound, can't disprove either. So it is incomplete.
§43.3 then strengthens the result by dropping the assumption that $T$ is sound in favour of the assumption of omega-consistency, together with the usual assumption that $T$ is (primitive) recursively axiomatized and includes a small amount of arithmetic (e.g. contains Robinson arithmetic Q  -- the crucial thing is being strong enough to represent the (primitive) recursive functions). Then we can prove that $T$ is incomplete, going via the unsolvability of the Halting Problem (it's a half-page proof in detail, so forgive me for not reproducing it here)!
