I'm trying to find a way to explain the idea of the Halting Problem proof in as accessible a manner as possible (to undergrad CS students). The simplest argument I have found is this one; this is precisely the style of treatment I am aiming for. However, the self-reference (in particular, checking if a program halts on itself) is not the most didactic.
What I'm wondering, as a proof sketch, is why we could not simplify even further and say: if we assume a program H(P,I)
for the Halting Problem that halts with true if P(I)
halts, and halts with false otherwise, then we could create a program of the form:
def Q(J):
if H(Q,J) then loop forever
else halt
... which is a valid program if and only if the Halting Problem is a valid program. We can then ask: what should H(Q,J)
return on any arbitrary value for J
? We see a contradiction in both possibilities, and we conclude that since the existence of H
allows us to construct the contradictory program Q
, thus a program of the form H
cannot exist.
There is still some self-reference here in that the program Q
checks whether or not it halts on the current input (and does the opposite), but for me, this seems much more intuitive than setting up a situation where we need a call of the form P(P)
or H(P,P)
, etc. However, I have not seen this simpler argument used, and I think it would have been were it valid. Hence my questions are:
- Is the above argument sufficient as a proof (sketch) of the Halting Problem?
- If so, why do so many arguments go with a confusing step of the form
P(P)
orH(P,P)
? (Is it just to remove the unimportant "input" from the equation?) - If not, what's missing?
- If so, why do so many arguments go with a confusing step of the form
There are a variety of related questions on this topic, such as:
- Halting problem without self-reference
- Is there a more intuitive proof of the halting problem's undecidability than diagonalization?
I also found mention of the proof based on Berry's paradox, which is quite appealing. Still, I have not yet managed to convince myself whether or not the specific argument above works (even if just for my own understanding; I feel I am perhaps missing something stupid and would like to know what it is).