Proof of the undecidability of the Halting Problem

Question

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

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$?

Answer 1

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.

Answer 2

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.

Answer 3

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.

Answer 4

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.