25
$\begingroup$

I'm having trouble understanding the proof of the undecidability of the Halting Problem.

http://computing.guide/wp-content/uploads/2014/12/HaltingProblem1.jpg

If $H(a,b)$ returns whether or not the program $a$ halts on input $b$, why do we have to pass the code of $P$ for both $a$ and $b$?

Why can't we feed $H()$ with $P$ and some arbitrary input, say, $x$?

$\endgroup$
  • $\begingroup$ Keep in mind that in the computational model being used here, any (encoded) input is allowed. There's no type checking or anything like that. You can always encode a program and pass it as an input to itself. $\endgroup$ – asmeurer Nov 2 '16 at 15:59
  • 2
    $\begingroup$ You could feed $H$ whatever input you want. The structure of this proof requires considering a particular input. $\endgroup$ – David Richerby Nov 2 '16 at 18:47
  • 1
    $\begingroup$ You can provide any input to the program. The aim is to find the contradiction. Theoretically the machine 'H' should work for all kind of inputs. Thus we consider one of all possible inputs, which leads to contradiction. $\endgroup$ – Ugnes Nov 2 '16 at 18:59
  • $\begingroup$ This proof is subtly flawed. Consider if I have an H() that works for everything but itself; that would still be a general solution to the Halting Problem. $\endgroup$ – Joshua Nov 3 '16 at 19:16
  • $\begingroup$ Related, possibly duplicate: cs.stackexchange.com/questions/42819/… $\endgroup$ – Ilmari Karonen Nov 3 '16 at 21:06
27
$\begingroup$

The proof aims to find a contradiction. You have to understand what the contradiction derived is, in order to understand why $P$ is used as an input to itself. The contradiction is, informally: if we have a machine H(a, b) that decides "a accepts b", then we can construct a machine that accepts machines that do not accept themselves. (Read that a few times until you get it.) The machine shown in the picture – let's call it $M$ – $M(P) = $ does $P$ not accept $\langle P \rangle$?

The contradiction happens when you ask: does $M$ accept $\langle M \rangle$? Try to work out the two options to see how there is a contradiction.

$M$ accepts $\langle M \rangle$ if and only if $M$ does not accept $\langle M \rangle$; this is clearly a contradiction.

This is why it is essential for the proof to run $P$ on itself not some arbitrary input. This is a common theme in impossibility proofs known as diagonal arguments.

$\endgroup$
38
$\begingroup$

Ignore the picture for a moment; we'll get to it shortly. The program $H(a, b)$ is supposed to be a halt tester: when we give $H$ an input of a program $a$ (think of $a$ as the listing of a program) and anything at all for $b$, $H(a, b)$ acts as follows

  1. If the program represented by $a$ halts when given $b$ as input, $H(a, b)$ will answer "yes". On the other hand, if the program described by $a$ runs forever when given input $b$ then $H(a, b)$ will answer "no".
  2. Importantly, program $H$ will always halt and give the correct answer for any pairs $(a, b)$.

The argument that $H$ is impossible to build relies on the action of a particular "perverse" program, $P$, one which uses $H$ as a subroutine. $P$ takes as its input a listing of any program, $x$, and does the following:

P(x) =
  run H(x, x)
  if H(x, x) answers "yes"
      loop forever
  else
      halt

It's not hard to see that

$P(x)$ will halt if and only if the program $x$ will run forever when given its own description as an input.

So far so good: $P$ will certainly be a program as long as its subroutine $H$ is a program.

Now return to the picture. What happens if $P$ is given its own description as input? The picture describes just that scenario: Let $p$ be the description of program $P$, then, substituting into the highlighted part above, we'll have

$P(p)$ will halt if and only if the program $P(p)$ will run forever.

Clearly, this paradoxical behavior is impossible, so we're forced to the conclusion that the subroutine $H$ cannot be a halt tester, since it fails in the one case, where it's given $(p, p)$ as input. There might be other cases where $H$ works as it should, but since $H$ fails in at least one situation, it cannot be a complete halt tester, as required.

$\endgroup$
  • $\begingroup$ I like this answer. Though now that I understand the proof, it just appears to prove that H can throw a recursion limit exception. $\endgroup$ – Fax Nov 2 '16 at 12:49
  • 2
    $\begingroup$ @Fax H isn't getting called more than once, there's no recursion in P whatsoever. H(P, P) doesn't execute P, it just "magically" determines whether or not P halts when passed itself. $\endgroup$ – Ajedi32 Nov 2 '16 at 19:52
  • $\begingroup$ @Ajedi32 H(P,P) doesn't have to execute P, but it has to execute H(x ↦ H(x,x), P) as part of determining if P halts. Which expands to H(x ↦ H(y ↦ H(y,y), x), P) and so on. $\endgroup$ – Fax Nov 3 '16 at 14:44
  • $\begingroup$ @Fax The implementation of H is not specified in this proof. So no, it doesn't have to execute anything, whether that be P or itself. The proof starts with the assumption that some sort of program H exists which magically decides the halting problem, then goes on to prove that the very existence of such a program would be a contradiction, and thus no such program exists. $\endgroup$ – Ajedi32 Nov 3 '16 at 15:07
  • 1
    $\begingroup$ @Fax You do raise a good point though about whether a program could exist which decides the halting problem except when called on itself. See Are there any proofs the undecidability of the halting problem that does not depend on self-referencing or diagonalization? for an interesting question about that. $\endgroup$ – Ajedi32 Nov 3 '16 at 15:25
9
$\begingroup$

Try a prettier proof with animations. And since ansewrs should contain more than just a link to a site, here's the answer to your question.

First, let us recall how the proof of non-existence of the Halting oracle works. We prove that given any candidate H for a Halting oracle, there is a program P and an input a for which H fails to predict correctly what P(a) does.

Theorem: Let H be any program which takes two inputs and always returns either halt or loop. Then there exists a program Q and an input a such that Q(a) halts if, and only if, H(Q,a) returns loop.

Proof. Consider the program

program P(y):
  if H(y,y) = halt then
    loop forever
  else:
    return

LetQ = P and a = P. Either H(Q,a) = halt or H(Q,a) = loop:

  • if H(Q,a) = halt then Q(a) (which is just P(P)) runs forever by the definition of P.
  • if H(Q,a) = loop then Q(a) halt by the definitoin of P.

QED

You asked why we considered H(P,P) instead of H(P,X) for some other X. The obvious answer is "because H(P,P) is what makes the proof work"! If you used H(P,X) for some arbitrary X, then you would get stuck. Indeed, the proof would then look like this:

Broken proof. Consider the program

program P(y):
  if H(y,y) = halt then
    loop forever
  else:
    return

LetQ = P and a = X for some arbitrary X. Either H(Q,X) = halt or H(Q,X) = loop:

  • suppose H(Q,X) = halt then we cannot tell what P(X) does, because whether P(X) halts depends on what H(X,X) returns. We are stuck. However, if we knew that P(X) and X(X) are the same, we could make progress. (So, we really should take X = P).
  • if H(Q,a) = loop then we are stuck again, and we would be unstuck if X = P.

No QED.

I hope this shows that we must consider H(P,P) in order to make our idea work.

$\endgroup$
  • $\begingroup$ Haha. Awesome! :) $\endgroup$ – aelguindy Nov 1 '16 at 23:28
2
$\begingroup$

The upshot of the proof is this analogy:

If a person $P$ claims s/he$_{(P)}$ can recognize the sentiment of every person $P^{\prime}$ when s/he$_{(P^{\prime})}$ sees something, then ask the claimant $P$ to emulate the opposite of that sentiment in everyone s/he$_{(P)}$ sees. And then put her/him$_{(P)}$ in front of a mirror. S/he$_{(P)}$ will just not know what sentiment to express. 🙂

The subscripts $_{(P)}$ and $_{(P^{\prime})}$ are used to disambiguate the pronouns.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.