Halting Problem without self-reference: why does this argument not suffice (or does it)?

Question

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) 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 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).

Answer 1

I don't think this is a good way to present the halting problem, because it sweeps a critical issue under the covers in a sneaky way. I suggest sticking with a more standard presentation, such as the one you linked. If you want to find a way to explain it in a way that minimizes the technical content, the presentation in this video is surprisingly accessible, and remains true to the logic of the standard proof.

On to the difficulties with your proposal. In your proposal, it's not trivial to write down the code for such a Q. Think about what it means to have the line

  if H(Q,J) then loop forever 

Recall that the first argument to H is a bit-string that contains the code / algorithm / Turing machine -- it's not a pointer to the function, but a string. Naively, this seems to mean that we include a hardcoded string that contains the source code for Q, inside the code of Q. But that's not possible. Suppose the code for Q takes 100 characters. Then we need to hardcode a 100-character string constant inside the definition of Q, plus we also need some more characters for the rest of the logic -- and that adds up to more than 100 characters. If you think about it, it's obvious that we can't have a string constant inside the code of Q that is the code of Q, because it would be too long.

Maybe you're thinking that's not what you had in mind. Maybe you were thinking that the programming language will have some built-in API to get the code of the current function, so actually the code you were thinking of is something like:

def Q(J):
  if H(get_source_code_of_current_function(),J) then loop forever
  else halt

OK, fine. This proves that the halting problem can't be solved for code written in any programming language that has a get_source_code_of_current_function() API. However, my favorite programming language doesn't have such an API. So, this proof doesn't prove anything about my favorite programming language -- perhaps the halting problem is solvable for my language, who knows? Similarly, Turing machines don't have such an API, so this doesn't prove that the halting problem for Turing machines is undecidable.

And that's a major flaw in your proof. And it's a flaw that is subtle and not at all evident. I don't think it's pedagogically a good idea to present a proof that "looks valid" on the surface but is actually, once you dig into it deeper, flawed.

Now, it is possible to rescue your proposed proof. It actually is possible to construct a function Q that works the way you said; you basically need it to be a quine. I suppose in principle you could explain the idea of quines, then present your proof and explain how to implement a function Q using those ideas. But that seems like a bad idea to me, from a pedagogical perspective. Quines are mind-bending and mysterious and freaking hard to understand. A student who doesn't understand quines won't understand your proof. And it makes the proof of undecidability for the halting problem look a lot more mysterious than it needs to be. So this does not seem to me like a more accessible way to understand the halting problem.

Answer 2

I don't see how self-reference is pedagogically difficult. The Barber Paradox is pretty easy to understand. And your argument has implicit self-reference, and I find it to be more difficult to understand than simple self-reference. On top of that, it's incoherent. To define H(Q,J), you first need to know what Q is, and to define Q, you first need to know what H(Q,J) is. That doesn't work. At best you can assert that Q is a fixed point of this self-referential definition, but then if you try to derive anything from the contradictory nature of Q, you're just showing H doesn't exist OR that no such fixed point exists; you now have to prove that if H did exist, the fixed point would have to exist.