Halting Problem without self-reference: why does this argument not suffice (or does it)?
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. 603
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) or H(P,P)? (Is it just to remove the unimportant "input" from the equation?)
* If not, what's missing?
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 <PERSON>'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). 603