Is there a more intuitive proof of the halting problem’s undecidability than diagonalization?

ignougroup
Problem Detail: I understand the proof of the undecidability of the halting problem (given for example in Papadimitriou’s textbook), based on diagonalization. While the proof is convincing (I understand each step of it), it is not intuitive to me in the sense that I don’t see how someone would derive it, starting from the problem alone. In the book, the proof goes like this: “suppose $M_H$ solves the halting problem on an input $M;x$, that is, decides whether Turing machine $M$ halts for input $x$. Construct a Turing machine $D$ that takes a Turing machine $M$ as input, runs $M_H(M;M)$ and reverses the output.” It then goes on to show that $D(D)$ cannot produce a satisfactory output. It is the seemingly arbitrary construction of $D$, particularly the idea of feeding $M$ to itself, and then $D$ to itself, that I would like to have an intuition for. What led people to define those constructs and steps in the first place? Does anyone have an explanation on how someone would reason their way into the diagonalization argument (or some other proof), if they did not know that type of argument to start with? Addendum given the first round of answers: So the first answers point out that proving the undecidability of the halting problem was something based on Cantor and Russell’s previous work and development of the diagonalization problem, and that starting “from scratch” would simply mean having to rediscover that argument. Fair enough. However, even if we accept the diagonalization argument as a well-understood given, I still find there is an “intuition gap” from it to the halting problem. Cantor’s proof of the real numbers uncountability I actually find fairly intuitive; Russell’s paradox even more so. What I still don’t see is what would motivate someone to define $D(M)$ based on $M$’s “self-application” $M;M$, and then again apply $D$ to itself. That seems to be less related to diagonalization (in the sense that Cantor’s argument did not have something like it), although it obviously works well with diagonalization once you define them. P.S. @babou summarized what was troubling me better than myself: “The problem with many versions of the proof is that the constructions seem to be pulled from a magic hat.”

Asked By : user118967

Answered By : Ilmari Karonen

In your edit, you write:

What I still don’t see is what would motivate someone to define $D(M)$ based on $M$’s “self-application” $M;M$, and then again apply $D$ to itself. That seems to be less related to diagonalization (in the sense that Cantor’s argument did not have something like it), although it obviously works well with diagonalization once you define them.

A common “popular” summarization of Turing’s proof goes something like this:

“If we had a machine $M_H$ that could decide whether another Turing machine halts or not, we could use this to construct another machine $D$ that, given a Turing machine $M$, would halt if and only if $M$ did not halt. But then we could pass $D$ as input to itself, and thus obtain a paradox: this machine would halt if and only if it did not halt!”

Now, it’s easy to see that the summarization above glosses over an important detail — the halting of the Turing machine $M$ also depends on its input, which we have not specified! But this issue can be fixed easily enough: we just need to have $D$ pick some suitable input $x_M$ for each input machine $M$, before passing them both to $M_H$. What’s a suitable choice for $x_M$, given that we ultimately want to derive a contradiction? Well, a natural choice is suggested directly by the “handwavy” proof above, where we ultimately obtain the contradiction by running the machine $D$ on itself. Thus, for the behavior of $D$ to really be paradoxical in this case, i.e. when invoked as $D(D)$, what we want is for the halting of $D(M)$ to depend on the behavior of $M$ when invoked as $M(M)$. This way, we’ll obtain the contradiction we want by setting $M = D$. Mind you, this is not the only choice; we could also have derived the same contradiction by, say, constructing a machine $D’$ such that $D'(M)$ halts if and only if $M(D’)$ (rather than $M(M)$) does not halt. But, whereas it’s clear that the machine $D$ can easily duplicate its input before passing it to $M_H$, it’s not quite so immediately obvious how to construct a machine $D’$ that would invoke $M_H$ with its own code as the input. Thus, using this $D’$ instead of $D$ would needlessly complicate the proof, and make it less intuitive.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/42819