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?)
14
-
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 WeharOct 23, 2019 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 UckoOct 23, 2019 at 0:23
-
1$\begingroup$ @MichaelWehar That's the main thing I'm not sure about. $\endgroup$– Solomon UckoOct 23, 2019 at 0:27
-
1$\begingroup$ This is sort of related to Chaitin's incompleteness theorem. $\endgroup$– Michael WeharOct 23, 2019 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 BiasiOct 23, 2019 at 10:03
|
Show 9 more comments
2 Answers
$\begingroup$
$\endgroup$
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.
$\begingroup$
$\endgroup$
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')$ for another arbitrary 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.
