Path: news.eternal-september.org!eternal-september.org!.POSTED!not-for-mail
From: Mikko <mikko.levanto@iki.fi>
Newsgroups: comp.theory
Subject: Re: How do simulating termination analyzers work? (V2)
Date: Tue, 24 Jun 2025 12:02:16 +0300
Organization: -
Lines: 112
Message-ID: <103dpio$1tstq$1@dont-email.me>
References: <1034bjk$6kj0$2@dont-email.me> <46077c7cead1d86f5f8c15d01c8f186d1c080515@i2pn2.org> <1034va2$bdkk$1@dont-email.me> <Hvx5Q.1274563$lZjd.1163517@fx05.ams4> <1038h4h$edae$1@dont-email.me> <1039bcv$k7rv$3@dont-email.me> <103av48$13v6g$1@dont-email.me> <103c0vl$1cme6$4@dont-email.me>
MIME-Version: 1.0
Content-Type: text/plain; charset=utf-8; format=flowed
Content-Transfer-Encoding: 8bit
Injection-Date: Tue, 24 Jun 2025 11:02:17 +0200 (CEST)
Injection-Info: dont-email.me; posting-host="3fdcce268bc98759ad6ce4f513657deb";
	logging-data="2028474"; mail-complaints-to="abuse@eternal-september.org";	posting-account="U2FsdGVkX1/22kA8GTIYb78oO9Zvt8ma"
User-Agent: Unison/2.2
Cancel-Lock: sha1:iYp60imoXbtXjLwP+L2LKHTNUAE=

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