# Turing meta-oracle

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?)

• 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? Oct 23, 2019 at 0:21
• @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. Oct 23, 2019 at 0:23
• @MichaelWehar That's the main thing I'm not sure about. Oct 23, 2019 at 0:27
• This is sort of related to Chaitin's incompleteness theorem. Oct 23, 2019 at 0:36
• 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. Oct 23, 2019 at 10:03

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