0
$\begingroup$

I have been doing a fair amount of research about the halting problem.

Most solutions I come across have the following pattern:

We assume we have a program H that solves the halting problem. We then define a new program P that takes a program x, and uses H(x) to figure out if x halts. If x does halt, then we make P go into an infinite loop. If x does not halt, we make P halt. Then, we run P(P). Then we get a contradiction because if P stops according to H(P), then P will actually not stop, and vice versa.

I currently assume that H takes a program which already has parameters plugged in to it. Proof: If this were not the case, we could write a simple program S that went "if input is true, halt. If input is false, run forever." Then, if H can just take the program S, not knowing what the input to S is, it seems trivial that there is no function H that can tell whether or not S will halt, since S halting depends on the input to S, and H doesn't know what the input to S is. Thus, I assume that H must be given a program whose inputs are specified.

Assuming this, it seems as though we are missing something when we run P(P). Since P(x) runs H(x), x needs to be a program with its inputs specified. Thus, we can't give P with no inputs as an input to P. Instead, we must give that second internal P some input.

Let's call the input x and assume that x's inputs are specified.

So we run P(P(x)):

P(x) will run H(x) to determine if x halts or not, and P(x) will do the opposite. Then, P(P(x)) will run H(P(x)) to determine if P(x) halts or not, and P(P(x)) will do the opposite. There's no contradiction anymore, since P(P(x)) is not the same thing as P(x).

So it seems like the only input to P that will make the proof work really is P. But if that's the case, then the inner P also needs to take P as an input, so we really need to be running P(P(P)) in order for the solution to work. But then that inner P also needs P as an input, so we really need infinite nest of functions, P(P(P(...))), in order for the proof to work.

Is there any solution to the halting problem that does not run into this issue?

|cite|improve this question
$\endgroup$
  • $\begingroup$ It looks as though the exact same question appears here: cs.stackexchange.com/questions/62911/… $\endgroup$ – Pro Q Feb 13 '18 at 7:16
  • $\begingroup$ There's a proof using Berry's paradox, which I wrote as an answer at least once on this site. $\endgroup$ – Yuval Filmus Feb 13 '18 at 7:49
  • $\begingroup$ I respectfully disagree with the statement that you have done a fair amount of research about the halting problem. A better description would be that you have invested a fair amount of thinking about the halting problem and trying to understand it. "Research" means that you're doing something new and original. $\endgroup$ – Andrej Bauer Feb 13 '18 at 11:33
  • $\begingroup$ @AndrejBauer I disagree with your definition of research, but agree with your explanation of what I have done. On stack exchange, looking into answers to your question before posting is required, and that's what I call "research". Obviously I didn't do enough, since I found a question that exactly asks mine after I had already posted. $\endgroup$ – Pro Q Feb 13 '18 at 20:43