-1
$\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 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 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 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 at 7:17
  • 4
    $\begingroup$ Possible duplicate of Proof of the undecidability of the Halting Problem $\endgroup$ – Pseudonym Jul 25 at 7:19
6
$\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.

$\endgroup$
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.

$\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 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 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 at 7:59
  • $\begingroup$ You have just described how the proof by contradiction goes. $\endgroup$ – Yuval Filmus Jul 25 at 8:00
  • $\begingroup$ "𝐻 could store the answers for selected pairs (𝑥,𝑦) in a table", I think this way just hide the simulation behind. It must simulate it, then put the results into the table. then select it. So in the deep end, the way it got the answer is:' simulate x on x and get the result.' $\endgroup$ – Anonemous Jul 25 at 8:16

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.