<p>Such an <span class="math-container">$H$</span> would let us solve the halting problem: </p>

<ul>
<li><p>We begin by running <span class="math-container">$H(H(P))$</span> until it halts (which it does by assumption on <span class="math-container">$H$</span>).</p></li>
<li><p>If the output of <span class="math-container">$H(H(P))$</span> is "doesn't halt," then we know <span class="math-container">$H(P)$</span> doesn't halt, and so by assumption on <span class="math-container">$H$</span> we know that <span class="math-container">$P$</span> doesn't halt. </p></li>
<li><p>If the output of <span class="math-container">$H(H(P))$</span> is "halts," then we subsequently run <span class="math-container">$H(P)$</span> until <em>it</em> halts; if <span class="math-container">$H(P)$</span> outputs "doesn't halt" then we know that <span class="math-container">$P$</span> doesn't halt, and if <span class="math-container">$H(P)$</span> outputs "halts" then we know that <span class="math-container">$P$</span> doesn't halt.</p></li>
</ul>

<p>The above procedure always halts and determines whether <span class="math-container">$P$</span> halts correctly.</p>

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

CC BY-SA 4.0
2020-01-06T18:06:01.273Z
2021-12-26T12:14:34.660Z
2021-12-26T12:14:34.660Z
Esa Pulkkinen
<p>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?)</p>

CC BY-SA 4.0
2019-10-23T00:21:26.283Z
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
CC BY-SA 4.0
2019-10-23T00:23:39.543Z
@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
CC BY-SA 4.0
2019-10-23T00:25:13.697Z
Sorry, I edited before you posted your reply.  The idea makes sense now.  :)
Michael Wehar
CC BY-SA 4.0
2019-10-23T00:26:04.417Z
So there are programs P where P does not terminate and we cannot prove in standard formal logic systems that P does not terminate.
Michael Wehar
CC BY-SA 4.0
2019-10-23T00:27:31.353Z
@MichaelWehar That's the main thing I'm not sure about.
Solomon Ucko
CC BY-SA 4.0
2019-10-23T00:36:17.293Z
This is sort of related to Chaitin's incompleteness theorem.
Michael Wehar
CC BY-SA 4.0
2019-10-23T01:25:19.327Z
I'm still a bit confused by your current post.  There is no program that solves the halting problem so there is no program Q that always terminates and determines whether or not P halts.  But, it sounds to me like that's not your question.  Originally, I thought you were asking if there exists a program P such that P does not terminate and there does not exist a proof that P does not terminate.  I think I can show this under reasonable consistency assumptions.  Could you possibly edit your question to clarify.  Thank you very much for your consideration.
Michael Wehar
CC BY-SA 4.0
2019-10-23T01:32:31.617Z
@MichaelWehar Isn't it possible to create a program that solves the halting program, but may or may not terminate? Also, I think I meant to ask about the computability of the computability of Q, i.e. the computability of the computability of the computability of P. I think I screwed up when changing my question from infinite recursion to this... I'll edit when I get a chance. Thanks, BTW.
Solomon Ucko
CC BY-SA 4.0
2019-10-23T01:46:18.103Z
The halting problem is computably enumerable (c.e.).  Essentially, this means that there exists a program Q such that for all P, Q terminates on the source code of P if and only if P terminates.  Please do edit the question.  I am looking forward to understanding your question.  :)
Michael Wehar
CC BY-SA 4.0
2019-10-23T02:17:12.400Z
@MichaelWehar Edited! Sorry for the confusing initial draft.
Solomon Ucko
CC BY-SA 4.0
2019-10-23T10:03:34.100Z
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
CC BY-SA 4.0
2019-10-23T10:33:50.730Z
@MarzioDeBiasi Good idea. I was wondering it's possible to find an H such that H(H(P)) terminates for all P, though.
Solomon Ucko
CC BY-SA 4.0
2019-10-23T10:42:26.180Z
@SolomonUcko: yuo can find an H that always terminate and outputs "Yes", "No" and "Don't know"; but having an H that outputs "Yes", "No" and always terminate means having an H that solves the halting problem ... which is impossible.
Marzio De Biasi
CC BY-SA 4.0
2019-10-23T10:48:16.507Z
@MarzioDeBiasi I meant that, although H may or may not terminate, $H\circ H$ should. H(P) must terminate if P does, though, which causes H(H(P)) to terminate.
Solomon Ucko
<computability><oracles><decidability><halting-problem><recursive>
Turing meta-oracle
Solomon Ucko
# Turing meta-oracle

(Asked by: username_0 on 2019-10-22)

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

**Tags:** computability, oracles, decidability, halting-problem, recursive

> **Comments:**
> **username_1**: 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?  
> **username_0**: @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.  
> **username_1**: Sorry, I edited before you posted your reply.  The idea makes sense now.  :)  
> **username_1**: So there are programs P where P does not terminate and we cannot prove in standard formal logic systems that P does not terminate.  
> **username_0**: @MichaelWehar That's the main thing I'm not sure about.  
> **username_1**: This is sort of related to Chaitin's incompleteness theorem.  
> **username_1**: I'm still a bit confused by your current post.  There is no program that solves the halting problem so there is no program Q that always terminates and determines whether or not P halts.  But, it sounds to me like that's not your question.  Originally, I thought you were asking if there exists a program P such that P does not terminate and there does not exist a proof that P does not terminate.  I think I can show this under reasonable consistency assumptions.  Could you possibly edit your question to clarify.  Thank you very much for your consideration.  
> **username_0**: @MichaelWehar Isn't it possible to create a program that solves the halting program, but may or may not terminate? Also, I think I meant to ask about the computability of the computability of Q, i.e. the computability of the computability of the computability of P. I think I screwed up when changing my question from infinite recursion to this... I'll edit when I get a chance. Thanks, BTW.  
> **username_1**: The halting problem is computably enumerable (c.e.).  Essentially, this means that there exists a program Q such that for all P, Q terminates on the source code of P if and only if P terminates.  Please do edit the question.  I am looking forward to understanding your question.  :)  
> **username_0**: @MichaelWehar Edited! Sorry for the confusing initial draft.  
> **username_2**: 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.  
> **username_0**: @MarzioDeBiasi Good idea. I was wondering it's possible to find an H such that H(H(P)) terminates for all P, though.  
> **username_2**: @SolomonUcko: yuo can find an H that always terminate and outputs "Yes", "No" and "Don't know"; but having an H that outputs "Yes", "No" and always terminate means having an H that solves the halting problem ... which is impossible.  
> **username_0**: @MarzioDeBiasi I meant that, although H may or may not terminate, $H\circ H$ should. H(P) must terminate if P does, though, which causes H(H(P)) to terminate.  

---

## 2 answers

### Answer by username_3 on 2019-12-29. Score: 4 | Accepted answer

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.


---

### Answer by username_4 on 2020-01-06. Score: -2

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.


---

