The Halting problem proof is wrong?

Question

First, let's see the pseudocode proof of halting problem:

P(x) =
  run H(x, x)
  if H(x, x) answers "yes"
      loop forever
  else
      halt

Then we have a problem:

When param x is the encoding string of P itself, the code line run H(x, x) will go to an infinite loop.

Because:

How does H know whether x halts on x?

The answer is H must simulate x on x, then it will call P(x) again and again, then go to an infinite recursive calling. So the pseudocode will stuck in this line run H(x, x), and never can continue. So I think the pseudocode proof is not correct.

Edit:

H seems like a future teller of P. no matter what H says about P, when P actually act x on x, P does the opposite of what H says, which shows that the future teller of P does not exist.

We know that future teller does not exist. so the H does not exist.

Answer 1

You are committing a logical error. This question has nothing whatsoever to do with computability and machines. It is entirely about how to prove that something does not exist. Namely, to show the statement $$\lnot \exists x . \phi(x)$$ we do as follows:

1. Assume that there is $x$ such that $\phi(x)$. We assume this even though perhaps we have no idea how to get such an $x$. We may even be of the opinion that there is no such $x$, but we assume there is one anyway, for the purposes of proving that there isn't one.
2. Working under the assumption that there is $x$ such that $\phi(x)$ we derive a contradiction. While deriving the contradiction, we need not worry where $x$ came from, or whether it is possible to have one, because we already assumed that there is one.

The proof of non-existence of the halting oracle takes this exact form: $$\lnot \exists H . \text{$H$ is a halting oracle}.$$ I apologize in advance for the ensuing bold text.

First we assume there exists a halting oracle $H$, that is a program $H$ which always terminates and correctly determines for every program and input whether the program run on the input will halt. We now work under the assumption that $H$ exists. We do not ask whether the assumption is actually correct, or how $H$ might look like. If our intuitions tell us that $H$ cannot exist, we disregrad them. In particular, we assumed ahead of time that $H$ works for all programs, including the ones that we might construct subsequently using $H$ itself. This is what it means to "work under a hypothesis".

Now, using the assumption that $H$ exists, we define $P$ and derive a contradiction. While we construct $P$ and think about how it works, we can use the standing assumption that $H$ always terminates and that it always answers correctly. It has to do so for $P$ as well because we assumed that it does for all programs. No amount of arguing will deny that assumption, no matter how counter-intuitive it is, because we assumed so.

Since our initial assumption of existence of $H$ lead to a contradiction, we may now drop the assumption that $H$ exists (we stop "working under a hypothesis") and conclude that $H$ does not exist.

Answer 2

First, let us see what the halting proof attempts to prove:

There is no program $H$ that, on input $(x,y)$, always halts, and returns whether the program encoded by $x$ halts when run on the input $y$.

We call the function which $H$ is supposed to compute the halting predicate.

The program you are suggesting, which consists of simulating a run of program $x$ on input $y$, definitely doesn't always halt. What we are attempting to show is that there is no other devious way to computing the halting predicate in a way which does always halt.

The proof you are describing is a proof by contradiction. We assume that there is a program $H$ that always halts and computes the halting predicate correctly. Under this assumption, we reach a contradiction. Hence the conclusion is that no such program exists.

How does $H$ know whether $x$ halts on $x$?

The assumption that the proof by contradiction is making is that there does exist an $H$ which computes the halting predicate. What the proof shows is that $H$ actually doesn't compute the halting predicate correctly. So $H$ cannot tell whether $x$ halts on $x$, and that is exactly what the proof shows.

The answer is $H$ must simulate $x$ on $x$.

This is not true. There are similar predicates which can be computed. For example, we can decide whether a program halts on all inputs within 100 steps. We can do so even though there are infinitely many potential inputs, and so the naive solution, which is to run the program on all inputs for 100 steps, can be improved.

What the proof shows is that there is no computable way to decide whether a given program $x$ halts on a given input $y$. It doesn't show that $H$ must simulate $x$ on $y$; indeed, $H$ could store the answers for selected pairs $(x,y)$ in a table, and for these pairs it could just return the correct answer by doing a table lookup. This approach can only handle finitely many pairs $(x,y)$, and the proof shows that no other computable approach works.

Answer 3

In your "pseudo-code proof", you left out an essential bit. We try to prove that there is no machine H, which for every input x, y halts and outputs "yes" if the machine x halts with input y, and halts and outputs "no" if the machine x doesn't halt with input y.

We do a proof by contradiction: We assume that H exists, and we show this leads to a contradiction. And because the assumption that h exists leads to a contradiction, the assumption must be false, so we proved that H didn't exist.

So the question "How does H know whether x halts on x?" doesn't make sense. We assume that H correctly decides whether x halts on x. We have no idea how H might do that. Actually, we want to prove that H cannot do this for every x. But for our indirect proof, we assume H can do this.

Next you say "H must emulate x". Well, emulating a turing machine to see whether it halts or not won't let you decide if the turing machine doesn't halt because the emulation won't ever finish. So that's not a good approach. Whatever H does, it's not going to emulate x. It must do something clever. As intelligent humans, we can use intelligence to decide for many x, y whether program x halts with input y. Sometimes we fail. But that might be because of lack of intelligence, not a problem with the input. We could imagine that there is a H that is intelligent enough to make the correct decision for every x, y.

So now we run H(x,x) where x is the encoding of P.

Due to our assumption, we know that H (x, x) halts, and it returns "yes" if P(x) halts and "no" if P(x) doesn't halt. How do we know this? Because that's our assumption that we use for the contradiction proof.

Does P(x) halt or not halt? It either halts or it doesn't.

If P(x) halts, then it first calls H(x,x). H(x, x) figures out correctly that P(x) halts, so H(x,x) outputs "yes", P(x) detects that H(x,x) did output "yes", so P(x) loops forever and doesn't halt. There we have a contradiction.

If P(x) doesn't halt, then it first calls H(x,x). H(x, x) figures out correctly that P(x) doesn't halt, so H(x,x) outputs "no" and then halts, P(x) detects that H(x,x) did output "no", not "yes", so P(x) stops immediately and halts. There we have again a contradiction.

So both "P(x) halts" and "P(x) doesn't halt" lead to a contradiction, therefore our assumption is wrong, therefore H doesn't exist. Bingo.

Two mistakes in your proof: 1. You assume that a halting checker would have to simulate a Turing machine. That’s not necessary. Actually it would be unlikely to work. 2. You assume that a non-halting program would end in a repeating pattern. That isn’t true at all. A Turing machine has an infinite state, so it can continue running without any pattern emerging.

Answer 4

If H(x,x) goes into an infinite loop, then that fact already proves that H does not solve the halting problem. If H solves the halting problem, then it never goes into an infinite loop.

If we are trying to figure out whether it's possible to solve the halting problem, we can ignore all the functions that sometimes enter infinite loops. They obviously don't solve the halting problem. Then only the ones that don't enter infinite loops are left, and those ones are disproved using the function P that you showed.