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.