Is the halting problem theorem really proven

Question

Here is a popular proof of the halting problem theorem:

Suppose there exist a procedure h(x, y) so that for any procedure p(x) and any data d, the execution of h(p, d) will halt, where halt means return by a "return" statement so a system crash means doesn't halt, and if h(p, d) returns 1 then the execution of p(d) will halt, otherwise h(p, d) returns 0 then the execution of p(d) will not halt.

Consider the following program:

001 h(x, y); // suppose the detail of h(x, y) is in a library.
002 
003 c(x) {
004   if (h(x, x) != 0) {
005     while(TRUE) {
006       ;
007     }
008   }
009   return 0;
010 }
011 
012 main() {
013   h(c, c);
014   c(c);
015 }

At line 13, if h(c, c) doesn’t halt, this is in contradiction with the claim of h(x, y).

If h(c, c) at line 13 returns 1, then when c(c) at line 14 is run, at line 4, the h(x, y) is in reality h(c, c) so it should return 1. Then, the program will go to line 5 which will start a perpetual loop. That is, c(c) will not halt which is in contradiction with h(c, c) returns 1 predicates c(c) will halt.

In another side, at line 13, if h(c, c) returns 0, the execution of line 4 when line 14 is running will be followed by the line 9. And c(c) will returns 0 which is in contradiction with h(c, c) returns 0 predicates c(c) will not halt.

So, either h(c, c) will not halt or it cannot predicate the behavior of c(c). So, such an h(x, y) as what is claimed cannot exist. That is, the halting problem is unsolvable.

But now the question is, what is the reason for the step "If h(c, c) at line 13 returns 1, then when c(c) at line 14 is run, at line 4, the h(x, y) is in reality h(c, c) so it should return 1" ?

The proof uses, in reality and implicitly, the hypothesis that the return value of h(x, y) depends uniquely on its parameters. Let's call this hypothesis the hypothesis h(c, c) = h(c, c) here. So, the proof proves in reality only that if h(x, y) depends only on its parameters, then h(x, y) cannot solve the halting problem of c(c), instead of proving the halting problem theorem.

To explain why h(x, y) should not depend only to its parameters, we can look at a metaphor: there are three persons P, C and A. C challenges P by saying “you cannot predicate whether I’ll go to bed this evening before or after 10 PM, let A be the arbiter”. Suppose it’s known by everyone that the strategy of C is to do what is contrary to whatever will be said by P. This is similar to the behavior of c(x) in the proof. If P announces his answer aloud, that is, gives the same answer to both C and A as supposed by the hypothesis h(c, c) = h(c, c), P will lose. But if P doesn’t announce his answer aloud, instead, he answers “before 10 PM” when he is asked by C and “after 10 PM” when he is asked by A, then, P will win. To require P to announce his answer aloud is just unfair. To limit the h(x, y) to depend uniquely on its parameters would be incorrect because it imposes a non relevant limit.

Moreover, the meaning of the return value of h(x, y) should be more precisely defined: its return value predicates the answer to the halting problem of p(d) if it were called at where h(p, d) is called.

With this more precisely defined h(x, y), it could be known that if c(c) were called inside c(c), it will not halt so the h(c, c) at line 4 should return 0. Then, the c(c) at line 14 will halt because the h(c, c) at line 4 returns 0. Then, the h(c, c) at line 13 should return 1. That is, h(x, y) can solve the halting problem of c(c) if it doesn't depend uniquely on its parameters.

Finally, to let h(x, y) doesn't depend only on its parameters is in reality possible. Who has some programming experiences would understand that it’s possible to construct the procedure call history by analyzing the system stack. In fact, most of the debuggers provide this service. That is, when the execution of a program is paused in a procedure, it’s possible to obtain a list of 2-tuplets (P(N), A(N)) N=0, 1, …, M, where P(N) is a procedure name, A(N) is the line number of the statement in P(N) at where P(N+1) is called. And it’s in P(M) at A(M) that the paused procedure was called.

If h(x, y) analyze also the system stack, then in the h(c, c) at line 13, it can know that it's called by main() at line 13. It's not called inside an execution of c(c). So, it should return the result of a complete analysis of c(c), that is, 1, to predicate c(c) will halt. When c(c) at line 14 is run, the h(c, c) at line 4 can know that main() at line 14 called c(c), and then it was called by c(c) at line 4. That is, it knows that it's called in an execution of c(c). So, it should return 0.

So, the ultimate question is, does the well known proof really proves the halting problem theorem ?

Answer 1

Any proof of the undecidability of the halting problem is specific to some model of computation. The proof is usually stated using Turing machines, which don't have call stacks or any other bells or whistles. For Turing machines, the assumption that the behaviour of any program (or, rather, machine) depends only on its inputs is completely valid.

You've changed the model of computation to some other system, which does have call stacks and possibly also bells and/or whistles, but you've not updated the proof to take this into account. In particular, you should consider the call stack to be a part of the input to the procedure, since you've proposed a mechanism by which it affects the output.

Answer 2

As David Richerby says, the details of the proof of the Halting Problem depend on the model of computation you're using. A proof using the lambda calculus will look very different from a proof using the Game of Life, though both proofs exist and work.

In this case, you seem to be using Turing machines as your model of computation. And a Turing machine has no concept of a program stack or subroutines: its output really does depend only on its input. Anything else, like a program stack, has to be either built into the machine (and therefore constant) or part of its input.

The key here is what's called the Universal Turing Machine Theorem, which basically says "given a Turing machine that computes f(x), and a Turing machine that computes g(x), you can build a Turing machine that computes f(g(x))". Here, these are functions in a mathematical sense: every input corresponds to one and only one output. The details are rather technical, but it involves using a Turing machine to simulate another Turing machine. (In fact, you can make a Turing machine that can simulate any other Turing machine. Hence "universal".)

So the reason why h(x,x) = h(x,x) is because h is at heart a Turing machine, and the output of a Turing machine depends only on its input.