0
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ @Fleeep code from: cs.stackexchange.com/a/65406/105746 it is almost same from wiki:en.wikipedia.org/wiki/Halting_problem#Proof_concept $\endgroup$ – Anonemous Jul 25 '19 at 6:53
  • $\begingroup$ The idea is exactly existence of a program which can answer if any problem halts or not without simulation. Like parse code and investigate its workflow. By the argument such program can’t exist. $\endgroup$ – Eugene Jul 25 '19 at 7:10
  • $\begingroup$ @Eugene then how does the parser know whether it halt? the parser may be told by another program/person, then how the another program know? ... eventually, at the deep end, they both end at one way: simulate x on x and see the result. $\endgroup$ – Anonemous Jul 25 '19 at 7:15
  • $\begingroup$ We assume such solver H(x) magically exists. We just know it returns yes or no in finite time. Please see comments from the answer in the question you mentioned. $\endgroup$ – Eugene Jul 25 '19 at 7:17
  • 4
    $\begingroup$ Possible duplicate of Proof of the undecidability of the Halting Problem $\endgroup$ – Pseudonym Jul 25 '19 at 7:19
7
$\begingroup$

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.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ I find the use of the term assume / assumption quite misleading. Unfortunately, it is the standard term. It would be clearer to use suppose. $\endgroup$ – reinierpost Mar 6 at 18:56
7
$\begingroup$

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.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ What if we add a restriction on P: "P does not accept the encoding string of P." then does the pseudocode stand? $\endgroup$ – Anonemous Jul 25 '19 at 7:37
  • $\begingroup$ I'm not sure what adding such a restriction means. Are you suggesting to modify $P$? Why would you do that? The current $P$ already proves what we want. I would guess that you are still unhappy about the proof. I suggest you take a few days to think it through and learn to accept it. $\endgroup$ – Yuval Filmus Jul 25 '19 at 7:40
  • $\begingroup$ The restriction is just a side problem which I also want to discuss. And I am happy to read you answer, but I am still confusing about the proof. Imagine If H say:"x halts on x", then if we run P(x), it must give the same result. but if it go to an infinite loop, then it shows that H does not tell the truth. so the assumption does not hold. Am I right? $\endgroup$ – Anonemous Jul 25 '19 at 7:59
  • 1
    $\begingroup$ I'm afraid you're wrong. A machine $H$ can lookup the answer in a table without first finding it. They're just there, part of its definition. $\endgroup$ – Yuval Filmus Jul 25 '19 at 8:18
  • 1
    $\begingroup$ You're having trouble with non-constructive proofs, which is understandable – many mathematicians had such issues at the turn of the 20th century. But we're long past that. There's absolutely no problem in assuming that a program knows the answer to the halting problem – or any other problem – for any finite number of inputs. Perhaps we can't write this program explicitly, but we know that it exists, and that's enough. $\endgroup$ – Yuval Filmus Jul 25 '19 at 8:24
0
$\begingroup$

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.

| cite | improve this answer | |
$\endgroup$

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.