Is there any concrete relation between Gödel's incompleteness theorem, the halting problem and universal Turing machines?

Question

I've always thought vaguely that the answer to the above question was affirmative along the following lines. Gödel's incompleteness theorem and the undecidability of the halting problem both being negative results about decidability and established by diagonal arguments (and in the 1930's), so they must somehow be two ways to view the same matters. And I thought that Turing used a universal Turing machine to show that the halting problem is unsolvable. (See also this math.SE question.)

But now that (teaching a course in computability) I look closer into these matters, I am rather bewildered by what I find. So I would like some help with straightening out my thoughts. I realise that on one hand Gödel's diagonal argument is very subtle: it needs a lot of work to construct an arithmetic statement that can be interpreted as saying something about it's own derivability. On the other hand the proof of the undecidability of the halting problem I found here is extremely simple, and doesn't even explicitly mention Turing machines, let alone the existence of universal Turing machines.

A practical question about universal Turing machines is whether it is of any importance that the alphabet of a universal Turing machine be the same as that of the Turing machines that it simulates. I thought that would be necessary in order to concoct a proper diagonal argument (having the machine simulate itself), but I haven't found any attention to this question in the bewildering collection of descriptions of universal machines that I found on the net. If not for the halting problem, are universal Turing machines useful in any diagonal argument?

Finally I am confused by this further section of the same WP article, which says that a weaker form of Gödel's incompleteness follows from the halting problem: "a complete, consistent and sound axiomatisation of all statements about natural numbers is unachievable" where "sound" is supposed to be the weakening. I know a theory is consistent if one cannot derive a contradiction, and a complete theory about natural numbers would seem to mean that all true statements about natural numbers can be derived in it; I know Gödel says such a theory does not exist, but I fail to see how such a hypothetical beast could possibly fail to be sound, i.e., also derive statements which are false for the natural numbers: the negation of such a statement would be true, and therefore by completeness also derivable, which would contradict consistency.

I would appreciate any clarification on one of these points.

Answer 1

I recommend you to check Scott Aaronson's blog post on a proof of the Incompleteness Theorem via Turing machines and Rosser's Theorem. His proof of the incompleteness theorem is extremely simple and easy to follow.

Answer 2

Neel Krishnaswami's answer to Halting problem, uncomputable sets: common mathematical proof? on CSTheory points to references connecting the above results under the umbrella of category theory.

Answer 3

(This is supposed to be a comment to Suresh's answer, but it's simply too long to fit there. So I apologize in advance that it doesn't really answer Marc's question.)

I find Neel's answer Halting problem, uncomputable sets: common mathematical proof? on CSTheory and Andrej Bauer's blog post unsatisfactory for two reasons.

First, we don't usually need all the category-theoretic jargon to explain the connection. The existence of an undecidable language is implied by Cantor's Theorem, which has a very elementary diagonal proof. The reason is that the set of programs is equinumerous to $\mathbb{N}$. On the other hand, since each language can be seen as a subset of $\mathbb{N}$, and thus the set of all languages is equinumerous to $\mathcal{P}(\mathbb{N})$. By Cantor's Theorem, there is no surjection from $\mathbb{N}$ onto $\mathcal{P}(\mathbb{N})$, and thus we know there must exist an undecidable language.

Second, the above proof is unsatisfactory since we also want to "see" example of a reasonable undecidable language. The above proof can be seen as a counting argument and thus not really "constructive" in that sense. Turing discovered the halting problem as such an example.

Answer 4

Universal Turing machines are useful for some diagonal arguments, e.g in the separation of some classes in the hierarchies of time or space complexity: the universal machine is used to prove there is a decision problem in $\mbox{DTIME}(f(n)^3)$ but not in $\mbox{DTIME}(f(n/2))$. (Better bounds can be found in the WP article)

However, to be perfectly honest, if you look closely, the universal machine is not used in the `negative' part: the proof supposes there is a machine $K$ that would solve a time-limited version of the halting problem and then proceeds to build $¬KK$. (No universal machine here) The universal machine is used to solve the time-limited version of the halting problem in a larger amount of time.

Answer 5

"If not for the halting problem, are universal Turing machines useful in any diagonal argument?"

Rice's theorem is essentially the generalization of diagonalization against Turing machines. It shows that there is absolutely no property about Turing machines that you can decide for all Turing machines with a single algorithm unless that property holds for all Turing machines or no Turing machines. Note the fact that the property holding for all Turing machines or no Turing machines prevents the diagonalization object from being a Turing machine, therefore it can't be on the list in the first place to contradict the decision about the property. Indeed this is the only thing that prevent the diagonalization object from being on the list and contradicting the decision about the property, which is all properties of Turing machines are undecidable. This pattern of the diagonalization object needing to be a member of the list of things that you're trying to make a decision about, and yet negate the decision, is the critical abstraction that Lawvere's theorem (referenced in the link in Suresh's answer) captures in order to fully generalize the notion of diagonalization. Now, since we know by experience that nearly every diagonalization seems to have the common property of leading to some extremely important result in mathematical logic, that makes Lawvere's theorem quite the interesting tool.