<pre><code>void Infinite_Loop() 
{
  HERE: goto HERE;
}

void Infinite_Recursion()
{
  Infinite_Recursion(); 
}

int main() 
{ 
  HHH(Infinite_Loop); 
  HHH(Infinite_Recursion); 
}
</code></pre>
<p>Any input that must be aborted to prevent the non termination of simulating termination analyzer HHH necessarily specifies non-halting behavior or it would never need to be aborted.</p>
<p>The above seems to be a tautology and is self-evidently true for the above two inputs.</p>
<p>It seems that HHH must compute the mapping from its finite string input to the behavior that this finite string specifies. This would seem to include the recursive call from DDD to HHH(DDD).</p>
<p>Do we report on the behavior before HHH aborts the simulation of its input or the behavior after this input has been aborted?</p>

CC BY-SA 4.0
2024-07-15T01:32:20.820Z
2024-07-15T22:13:15.163Z
2024-07-15T22:13:15.163Z
polcott
<p>What is the correct halt status for an input to a simulating termination analyzer that calls its own termination analyzer?</p>
<pre><code>typedef void (*ptr)();
int HHH(ptr P);

void DDD()
{
  HHH(DDD);
}

int main()
{
  HHH(DDD);
}
</code></pre>
<p>The above is a research level question because it is the simplest possible concrete example that is isomorphic to the key element of the Peter Linz Halting Problem proof (full proof provided below).</p>
<p>The key element is an input to a termination analyzer / partial halt decider that was defined to call its own analyzer / decider. <br><strong>When the halt status decision is based on the behavior of the input from UTM simulation by embedded_H we get surprising new results.</strong></p>
<pre><code>When Ĥ is applied to ⟨Ĥ⟩     
Ĥ.q0 ⟨Ĥ⟩ ⊢* embedded_H ⟨Ĥ⟩ ⟨Ĥ⟩ ⊢* Ĥ.qy ∞ 
Ĥ.q0 ⟨Ĥ⟩ ⊢* embedded_H ⟨Ĥ⟩ ⟨Ĥ⟩ ⊢* Ĥ.qn   

(a) Ĥ copies its input ⟨Ĥ⟩ 
(b) Ĥ invokes embedded_H ⟨Ĥ⟩ ⟨Ĥ⟩ 
(c) embedded_H simulates ⟨Ĥ⟩ ⟨Ĥ⟩ 
(d) simulated ⟨Ĥ⟩ copies its input ⟨Ĥ⟩ 
(e) simulated ⟨Ĥ⟩ invokes simulated embedded_H ⟨Ĥ⟩ ⟨Ĥ⟩ 
(f) simulated embedded_H simulates ⟨Ĥ⟩ ⟨Ĥ⟩ 
(g) goto (d) with one more level of simulation 
</code></pre>
<p>When embedded_H computes the mapping from its input finite string ⟨Ĥ⟩ ⟨Ĥ⟩ to the behavior that this input specifies then it is clear that embedded_H must abort the simulation of this input to prevent its own non-termination.</p>
<p><a href="https://i.sstatic.net/9tpXE.png" rel="nofollow noreferrer"><img src="https://i.sstatic.net/9tpXE.png" alt="enter image description here" /></a></p>
<p><strong>Linz, Peter 1990</strong>. An Introduction to Formal Languages and Automata. Lexington/Toronto: D. C. Heath and Company. (318-320)</p>

<decidability><undecidability>
What is the correct halt status for an input to a simulating termination analyzer that calls its own termination analyzer?
polcott
# What is the correct halt status for an input to a simulating termination analyzer that calls its own termination analyzer?

(Asked by: username_0 on 2024-07-05)

What is the correct halt status for an input to a simulating termination analyzer that calls its own termination analyzer?
typedef void (*ptr)();
int HHH(ptr P);

void DDD()
{
  HHH(DDD);
}

int main()
{
  HHH(DDD);
}

The above is a research level question because it is the simplest possible concrete example that is isomorphic to the key element of the Peter Linz Halting Problem proof (full proof provided below).
The key element is an input to a termination analyzer / partial halt decider that was defined to call its own analyzer / decider. When the halt status decision is based on the behavior of the input from UTM simulation by embedded_H we get surprising new results.
When Ĥ is applied to ⟨Ĥ⟩     
Ĥ.q0 ⟨Ĥ⟩ ⊢* embedded_H ⟨Ĥ⟩ ⟨Ĥ⟩ ⊢* Ĥ.qy ∞ 
Ĥ.q0 ⟨Ĥ⟩ ⊢* embedded_H ⟨Ĥ⟩ ⟨Ĥ⟩ ⊢* Ĥ.qn   

(a) Ĥ copies its input ⟨Ĥ⟩ 
(b) Ĥ invokes embedded_H ⟨Ĥ⟩ ⟨Ĥ⟩ 
(c) embedded_H simulates ⟨Ĥ⟩ ⟨Ĥ⟩ 
(d) simulated ⟨Ĥ⟩ copies its input ⟨Ĥ⟩ 
(e) simulated ⟨Ĥ⟩ invokes simulated embedded_H ⟨Ĥ⟩ ⟨Ĥ⟩ 
(f) simulated embedded_H simulates ⟨Ĥ⟩ ⟨Ĥ⟩ 
(g) goto (d) with one more level of simulation 

When embedded_H computes the mapping from its input finite string ⟨Ĥ⟩ ⟨Ĥ⟩ to the behavior that this input specifies then it is clear that embedded_H must abort the simulation of this input to prevent its own non-termination.

Linz, Peter 1990. An Introduction to Formal Languages and Automata. Lexington/Toronto: D. C. Heath and Company. (318-320)

**Tags:** decidability, undecidability

---

## 1 answers

### Answer by username_0 on 2024-07-15. Score: -2 | Accepted answer

void Infinite_Loop() 
{
  HERE: goto HERE;
}

void Infinite_Recursion()
{
  Infinite_Recursion(); 
}

int main() 
{ 
  HHH(Infinite_Loop); 
  HHH(Infinite_Recursion); 
}

Any input that must be aborted to prevent the non termination of simulating termination analyzer HHH necessarily specifies non-halting behavior or it would never need to be aborted.
The above seems to be a tautology and is self-evidently true for the above two inputs.
It seems that HHH must compute the mapping from its finite string input to the behavior that this finite string specifies. This would seem to include the recursive call from DDD to HHH(DDD).
Do we report on the behavior before HHH aborts the simulation of its input or the behavior after this input has been aborted?


---

