# 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? – Michael Wehar Oct 23 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. – Solomon Ucko Oct 23 at 0:23
• @MichaelWehar That's the main thing I'm not sure about. – Solomon Ucko Oct 23 at 0:27
• This is sort of related to Chaitin's incompleteness theorem. – Michael Wehar Oct 23 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. – Marzio De Biasi Oct 23 at 10:03