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 ?
h(x, x)
, instead, it simulatesh(x, x)
on a hypothetical global status (including the call stack) that is the same as the global status whenh(c, c)
is called in line 13. $\endgroup$ – xskxzr Jun 8 '18 at 3:02