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

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.