Re: How do simulating termination analyzers work? (V2)

Liste des GroupesRevenir à theory 
Sujet : Re: How do simulating termination analyzers work? (V2)
De : mikko.levanto (at) *nospam* iki.fi (Mikko)
Groupes : comp.theory
Date : 24. Jun 2025, 10:02:16
Autres entêtes
Organisation : -
Message-ID : <103dpio$1tstq$1@dont-email.me>
References : 1 2 3 4 5 6 7 8
User-Agent : Unison/2.2
On 2025-06-23 16:56:21 +0000, olcott said:

On 6/23/2025 2:18 AM, Mikko wrote:
On 2025-06-22 16:35:42 +0000, olcott said:
 
On 6/22/2025 4:07 AM, Mikko wrote:
On 2025-06-21 12:24:07 +0000, Mr Flibble said:
 
On Fri, 20 Jun 2025 19:44:50 -0500, olcott wrote:
 
On 6/20/2025 7:01 PM, Richard Damon wrote:
On 6/20/25 3:08 PM, olcott wrote:
void Infinite_Recursion()
{
   Infinite_Recursion(); return;
}
 void Infinite_Loop()
{
   HERE: goto HERE;
   return;
}
 void DDD()
{
   HHH(DDD);
   return;
}
 int Sipser_D()
{
   if (HHH(Sipser_D) == 1)
     return 0;
   return 1;
}
 int DD()
{
   int Halt_Status = HHH(DD);
   if (Halt_Status)
     HERE: goto HERE;
   return Halt_Status;
}
 My claim is that each of the above functions correctly simulated by
any termination analyzer HHH that can possibly exist will never stop
running unless aborted by HHH.
 The problem is that NO "Simulating Halt Decider" HHH, can correctly
simulte ANY of those inputs.
 For the first two, it is possible for a smart enough Simulation Halt
Decider to determine that the correct simulation of the input will not
halt, no matter what HHH actually does, since it doesn't depend on the
decider.
 For the last 3, it can not prove that they will not halt, as, in fact,
 
the correct simulation of all those inputs *WILL* halt
 _DDD()
[00002192] 55             push ebp [00002193] 8bec           mov ebp,esp
[00002195] 6892210000     push 00002192 [0000219a] e833f4ffff     call
000015d2  // call HHH [0000219f] 83c404         add esp,+04 [000021a2]
5d             pop ebp [000021a3] c3             ret Size in
bytes:(0018) [000021a3]
 Exactly how would N instructions of DDD emulated by HHH according to the
semantics of the x86 language reach machine address 000021a3 ?
 This exchange between **Peter Olcott** and **Richard Damon** is a clash
over the semantics of simulation, halting behavior, and what it means to
*correctly analyze* a self-referential or looping function using a
theoretical "termination analyzer" (`HHH`).
 Let’s break this down across three layers: **technical validity**,
**semantic precision**, and **communication clarity**.
 ---
 ## 🔍 1. **Olcott's Argument**
 Olcott gives a series of functions that are meant to illustrate programs
that either:
 * Loop infinitely in a trivially detectable way (`Infinite_Loop`,
`Infinite_Recursion`), or
* Engage in **self-referential calls to the analyzer** (`HHH`) to simulate
undecidable or paradoxical behavior (`DDD`, `Sipser_D`, `DD`).
 He claims:
 
Any HHH that correctly simulates these programs will never stop running
 As soon as he writes "any HHH" he falls in the trap called "equivocation".
 Likewise when I say that every integer N > 6 is > 5
 No, that is not the same. Instead that is provable from the transitivity
of >.
 The semantics of the C programming language conclusively
proves that DDD correctly simulated by any STA that can
possibly exist cannot possibly reach its own "return"
instruction final halt state.
Not whithout an unambiguous definition of "STA" and a sufficient
specification of HHH.
--
Mikko

Date Sujet#  Auteur
20 Jun 25 * How do simulating termination analyzers work? (V2)22olcott
21 Jun 25 +* Re: How do simulating termination analyzers work? (V2)16Richard Damon
21 Jun 25 i`* Re: How do simulating termination analyzers work? (V2)15olcott
21 Jun 25 i +* Re: How do simulating termination analyzers work? (V2)7olcott
21 Jun 25 i i`* Re: How do simulating termination analyzers work? (V2)6olcott
22 Jun 25 i i `* Re: How do simulating termination analyzers work? (V2)5Richard Damon
22 Jun 25 i i  `* Re: How do simulating termination analyzers work? (V2)4olcott
22 Jun 25 i i   `* Re: How do simulating termination analyzers work? (V2)3Richard Damon
24 Jun 25 i i    `* Re: How do simulating termination analyzers work? (V2)2Richard Heathfield
24 Jun 25 i i     `- Re: How do simulating termination analyzers work? (V2)1olcott
21 Jun 25 i +- Re: How do simulating termination analyzers work? (V2)1Richard Damon
22 Jun 25 i `* Re: How do simulating termination analyzers work? (V2)6Mikko
22 Jun 25 i  `* Re: How do simulating termination analyzers work? (V2)5olcott
23 Jun 25 i   `* Re: How do simulating termination analyzers work? (V2)4Mikko
23 Jun 25 i    `* Re: How do simulating termination analyzers work? (V2)3olcott
24 Jun 25 i     `* Re: How do simulating termination analyzers work? (V2)2Mikko
24 Jun 25 i      `- Re: How do simulating termination analyzers work? (V2)1olcott
21 Jun 25 `* Re: How do simulating termination analyzers work? (V2)5Mikko
21 Jun 25  `* Re: How do simulating termination analyzers work? (V2)4olcott
21 Jun 25   +* Re: How do simulating termination analyzers work? (V2)2Richard Damon
22 Jun 25   i`- Re: How do simulating termination analyzers work? (V2)1Mikko
22 Jun 25   `- Re: How do simulating termination analyzers work? (V2)1Mikko

Haut de la page

Les messages affichés proviennent d'usenet.

NewsPortal