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

82

29

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.

Marc van Leeuwen

Posted 2012-03-15T16:43:28.693

Reputation: 923

You have one conceptual problem: algorithmic decidability (Halting problem) and derivability resp. provability (logics) are two very different concepts; you seem to use "decidability" for both. – Raphael – 2012-03-15T18:10:47.357

yes indeed the two proofs are conceptually extremely similar and in fact one way to look at it is that Godel constructed a sort of turing-complete logic in arithmetic. there are many books that point out this conceptual equivalence. eg Godel Escher Bach by hofstadter or Emperors New Mind by penrose.... – vzn – 2012-10-11T16:19:51.807

1@Raphael: I am very well aware that there is a large conceptual difference between the statements of incompleteness theorem and of the undecidability of the halting problem. However the negative form of incompleteness: a sufficiently powerful formal system cannot be both consistent and complete, does translate into an indecidability statement: since the set of theorems deducible in a formal system is semi-decidable by construction, completeness would make the set of non-theorems semi-decidable as well (as negations of theorems, assuming consistency, or else as the empty set), hence decidable. – Marc van Leeuwen – 2012-03-17T18:04:56.457

Somewhat related ... I always misremember Hofstadter's parabel where the Tortoise keeps breaking Achilles' record player, as applying to the halting problem. In fact, I found this thread by (re)searching my confusion. I still feel the parabel translates more naturally and directly to the halting problem, but this is without any deep understanding of either theorem. – micans – 2018-07-19T14:12:04.793

Answers

35

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.

Marcos Villagra

Posted 2012-03-15T16:43:28.693

Reputation: 516

Thank you for this link, I'll accept for now as this comes closest to my concerns. At first I was quite disturbed though: I misunderstood "complete" to mean "every truth is a derivable" (a converse to sound) rather than "if $P$ is not derivable then $\lnot P$ is" (a converse to consistent). Scott Aaronson seems beleive the meaning of "complete" is evident to the audience, although he doesn't seem to assume a logician audience (which I certainly am not); with my misunderstanding what he writes makes no sense. Having found my error, I find the post quite interesting. – Marc van Leeuwen – 2012-03-24T15:53:51.890

1

There is another proof in a similar vein in the book The Nature of Computation (http://www.amazon.com/gp/cdp/member-reviews/A2DGFHJVZ92HVI/ref=ya_26?ie=UTF8&sort_by=MostRecentReview) in the chapter about computability. There, the authors avoid the use of Rosser's theorem and only assume the existence of universal machines (i.e., Church-Turing Thesis). The exact reference is section 7.2.5 page 238.

– Marcos Villagra – 2012-03-25T01:36:34.917

21

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.

Suresh

Posted 2012-03-15T16:43:28.693

Reputation: 5 269

1this paper is not mentioned in the cstheory answer (but is in the comments of Andrej Bauer's blog post from the answer), but is probably a good overview as well. – Artem Kaznatcheev – 2012-03-15T18:03:08.287

This is a connection based on similarity of proofs, rather than implications between the results, isn't it? – Raphael – 2012-03-15T18:11:42.080

1Well, the view in the paper that Artem links to is that these are all manifestations of a single category-theoretic fact. – Suresh – 2012-03-15T19:37:23.343

16

(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.

Dai

Posted 2012-03-15T16:43:28.693

Reputation: 1 362

1But diagonal argument is indeed a constructive proof. Along your reduction to Cantor's Theorem, the undecidable language is the set of all the machines whose encoding is not in its accepted language. – Willard Zhan – 2018-03-05T15:44:35.837

+1 This is a more simple approach, but I still doubt about this: "and thus we know there must exist an undecidable language." Could you specify the difference between undecidable language and undecidable problem? – Hernan_eche – 2012-05-15T16:24:17.143

1@Hernan_e There's no "difference" really. A decision problem in computation theory can be defined as any yes-or-no question on the set of inputs $x\in \Sigma^$. Thus, we can assign each decision problem $P$ to the set $L\subseteq \Sigma^$ of inputs for which the answer is yes. The set $L$ is the language defined by the problem $P$. – Dai – 2012-05-17T22:57:42.330

Understood, you are very clear, I agree the counting argument is not totally satisfactory, but even without the example, I think perhaps the worst part is that $L\subseteq \Sigma^*$ is infinite, then there is no big surprise in saying there are undecidable languages, would be great to extend (better said to limit) the reasoning for a finite case, ( I am not asking for an example of an undecidable problem), but a similar proof (or disproof) being valid for a finite set of input admited instead of $\mathbb{N}$ – Hernan_eche – 2012-05-18T18:05:28.707

6

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.

jmad

Posted 2012-03-15T16:43:28.693

Reputation: 9 129

For sufficiently nonconstant f(n). – Yonatan N – 2012-08-07T22:24:20.390

3

A slightly weaker form of Gödel's first incompleteness theorem can be derived from the undecidability of the Halting problem with a short proof. The full incompleteness theorems also have a short proof which is similar to the one for undecidability of the Halting problem. I highly recommend the whole series (or at least the previous part) for context. The proofs are based on Ryan O’Donnell's brilliant course slides.)

Julius Kunze

Posted 2012-03-15T16:43:28.693

Reputation: 131

0

"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.

stoopkid

Posted 2012-03-15T16:43:28.693

Reputation: 1

Asked: 2012-03-15T16:43:28.693

Viewed: 13 920 times

Active: 2020-03-27T21:06:54.223