1
$\begingroup$

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 ?

Improve this question
$\endgroup$
4
  • $\begingroup$ "To limit the h(x, y) to depend uniquely on its parameters would be incorrect because it imposes a non relevant limit." Why do you consider this not relevant? $\endgroup$ – Noah Schweber Jun 7 '18 at 18:14
  • $\begingroup$ For your model, you can revise the proof such that in line 4, it does not really call h(x, x), instead, it simulates h(x, x) on a hypothetical global status (including the call stack) that is the same as the global status when h(c, c) is called in line 13. $\endgroup$ – xskxzr Jun 8 '18 at 3:02
  • $\begingroup$ If you ask someone to do a work without any limit. Is it relevant to raise then a condition ? When P challenged by C, is it relevant to suppose that P will announce his answer aloud ? $\endgroup$ – user49413 Jun 11 '18 at 16:36
  • $\begingroup$ Yes, h(x, y) produces its answer by simulating the the execution of x(y). And a simulation MUST produce the same result as the effective execution. A program MUST be consistent, or in other words, be determined, that is, it should produce the same result when being executed in the same situation. The problem is: being called in the same situation doesn't mean being called with the same parameters because at where it's called makes also part of the situation being called. For example, if c(c) halts when being called in main(), it won't halt when being called in c(c). $\endgroup$ – user49413 Jun 11 '18 at 16:48
8
$\begingroup$

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.

Improve this answer
$\endgroup$
15
  • $\begingroup$ If Turing machine has no stack, how c(x) calls h(x, x) then receives the result ? $\endgroup$ – user49413 Jun 7 '18 at 17:50
  • $\begingroup$ Stack is in the memory. Memory is the tape in Turing machine. So, the stack is written and read by the program. It's not data, or in other words, the input data which is written before the start of the program running. $\endgroup$ – user49413 Jun 7 '18 at 17:52
  • $\begingroup$ Turing machine is the model of the modern computer. Can we imagine a computer without stack ? If Turing machine has no stack, how it could be the model of a computer ? Stack is the realization of a program that needs to call another program. Computer support its realization for reason of performance only. $\endgroup$ – user49413 Jun 7 '18 at 18:05
  • 4
    $\begingroup$ "Turing machine is the model of the modern computer." No, no, no. Turing machines have a very specific, precise definition and, actually, that definition doesn't look anything much like an actual computer. Turing defined the machines before digital computers even existed and Turing was, more or less, trying to formalize what a person could compute, using a pencil and paper. As an intuition, modern computers can simulate Turing machines and vice-versa, but that isn't the defintion. $\endgroup$ – David Richerby Jun 7 '18 at 20:40
  • 1
    $\begingroup$ I have explained the problem with your reasoning several times. I'm not going to do it again. $\endgroup$ – David Richerby Jun 11 '18 at 17:46
4
$\begingroup$

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.

Improve this answer
$\endgroup$
2
  • $\begingroup$ So, this Turing machine with the assumption of h(x, y) = h(x, y) cannot solve the halting problem of all programs. But this doesn't mean that the halting problem is unsolvable. It means only that the halting problem cannot be solved by this kind of Turing machine. $\endgroup$ – user49413 Jun 11 '18 at 16:13
  • $\begingroup$ It should be indicated that the tape in a Turing machine is a RAM not a ROM. That is, a specific place on the tape can be read and write repeatedly and alternatively. The data in stack is generated and used during an execution in the same zone of memory. Why and how it could be an input data or constant ? $\endgroup$ – user49413 Jun 11 '18 at 16:21

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.