0
$\begingroup$

Let H(P) be some program that given P('s source code) computes whether or not P terminates, i.e. solves the halting problem. H only needs to terminate if P terminates. (This disallows solutions like making the inner program stall indefinitely so the outer program can always return false.) Does there exist an H such that for all P, H(H(P)) terminates? (If not, is this possible with more nesting? What about infinite nesting, wherein P is started, then H(P), then H(H(P)), etc, and stops once any of them terminates?)

$\endgroup$
  • 1
    $\begingroup$ I'm still trying to understand. Is P a program with no inputs? Is Q a program that reads in P's source code as its only input? Do you mean that if P terminates, then Q terminates on the source code of P, but not necessarily the other direction? $\endgroup$ – Michael Wehar Oct 23 '19 at 0:21
  • 1
    $\begingroup$ @MichaelWehar P has no input. Q has P('s source code) as it's only input. Q terminates given P if P terminates, but if P does not terminate, Q can still terminate if it can prove that P cannot terminate. $\endgroup$ – Solomon Ucko Oct 23 '19 at 0:23
  • 1
    $\begingroup$ @MichaelWehar That's the main thing I'm not sure about. $\endgroup$ – Solomon Ucko Oct 23 '19 at 0:27
  • 1
    $\begingroup$ This is sort of related to Chaitin's incompleteness theorem. $\endgroup$ – Michael Wehar Oct 23 '19 at 0:36
  • 2
    $\begingroup$ What does it mean "H only needs to terminate if P terminates"?!? If taken literally, just pick H=P (or H=SimulationOf(P) ); and every finite application of H (e.g. H(H(P))) is simply the Halting problem for P (so such H cannot exist). But if you COULD grab the result of an "infinite recursion" as a single output then you can use this H : simulate P for 100 steps and leave as output a program P' that first rewrite the tape content after 100 steps and then replicate P from the state after 100 steps; then H always terminate and H(H(...H(P)) halts if and only if P terminates. $\endgroup$ – Marzio De Biasi Oct 23 '19 at 10:03
1
$\begingroup$

Such an $H$ would let us solve the halting problem:

  • We begin by running $H(H(P))$ until it halts (which it does by assumption on $H$).

  • If the output of $H(H(P))$ is "doesn't halt," then we know $H(P)$ doesn't halt, and so by assumption on $H$ we know that $P$ doesn't halt.

  • If the output of $H(H(P))$ is "halts," then we subsequently run $H(P)$ until it halts; if $H(P)$ outputs "doesn't halt" then we know that $P$ doesn't halt, and if $H(P)$ outputs "halts" then we know that $P$ doesn't halt.

The above procedure always halts and determines whether $P$ halts correctly.

$\endgroup$
0
$\begingroup$

Choose P arbitrarily (since question asks this for all P). Wouldn't constructing $H(H(P))$ already include assumption that $H(P)$ as input to $H$ has source code or other representation that can be tested for termination? If that is true, then $H(P)$ by assumption contains an implementation of solution to the halting problem for $P$, therefore executing that program solves the halting problem for $P$. Therefore $H(H(P))$ returns true. Thus, if $H$ is a termination checker, therefore running with input $P$ produces data as to whether $P$ terminates, a contradiction since halting problem for arbitrary $P$ is undecidable. If $H(P)$ doesn't have source code, then $H(H(P))$ should return false, the halting problem of $P$ cannot be solved by $H(P)$ since it doesn't terminate and your assumption that $H$ is a termination checker is wrong, a contradiction. The remaining alternative is that the arbitrarily chosen $P$ doesn't have valid representation. Thus $H$ validates its inputs and $H(P)$ returns false. But since P was arbitrary we can choose $P := H(P)$ since $H$ exists by assumption so by substitution $H(H(P))$ is false, but $H(P)$ terminates, so $H$ is not a termination checker, a contradiction.

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