Path: ...!eternal-september.org!feeder3.eternal-september.org!news.eternal-september.org!.POSTED!not-for-mail
From: "Fred. Zwarts" <F.Zwarts@HetNet.nl>
Newsgroups: comp.theory
Subject: Re: DDD correctly emulated by HHH is Correctly rejected as
 non-halting V2
Date: Mon, 15 Jul 2024 21:15:50 +0200
Organization: A noiseless patient Spider
Lines: 209
Message-ID: <v73sh7$qkp2$4@dont-email.me>
References: <v6rg65$32o1o$3@dont-email.me>
 <97e0632d0d889d141bdc6005ce6e513c53867798@i2pn2.org>
 <v6sdlu$382g0$1@dont-email.me> <v6td3a$3ge79$1@dont-email.me>
 <v6tp1j$3imib$2@dont-email.me> <v6trdu$3irhh$1@dont-email.me>
 <v6tu01$3imib$11@dont-email.me>
 <a177dd76613794d6bb877c65ffe6c587a8f31bc1@i2pn2.org>
 <v6tvpv$3imib$14@dont-email.me>
 <091e8b7baeea467ee894b1c79c8943cb9773adb7@i2pn2.org>
 <v6u346$3khl8$1@dont-email.me>
 <16ac79611a441e7e01119631051f69119eee958a@i2pn2.org>
 <v6v06i$3pivt$1@dont-email.me>
 <23cb2d2401b87bf4f6a604aa1a78b93ffc9a29bc@i2pn2.org>
 <v6v2t1$3pmjn$3@dont-email.me>
 <3fc6548531f91ed14a27420caf9679a634573ed0@i2pn2.org>
 <v70lmo$61d8$1@dont-email.me>
 <8a6e6d9ff49aabe2525ce5729a439c807de4768a@i2pn2.org>
 <34Ocnd4voeWlDAn7nZ2dnZfqnPudnZ2d@brightview.co.uk>
 <v725d7$hlvg$1@dont-email.me> <v72n0a$jtol$1@dont-email.me>
 <v735ah$mjis$4@dont-email.me>
MIME-Version: 1.0
Content-Type: text/plain; charset=UTF-8; format=flowed
Content-Transfer-Encoding: 8bit
Injection-Date: Mon, 15 Jul 2024 21:15:51 +0200 (CEST)
Injection-Info: dont-email.me; posting-host="11cf5ed0512e2277f3e9eeb7013e4f25";
	logging-data="873250"; mail-complaints-to="abuse@eternal-september.org";	posting-account="U2FsdGVkX19JGQEA0ENn1Fw+7SKC9bU6"
User-Agent: Mozilla Thunderbird
Cancel-Lock: sha1:LvUTrJOAlLnvo2GpHpWlIsS9RZs=
Content-Language: en-GB
In-Reply-To: <v735ah$mjis$4@dont-email.me>
Bytes: 10484

Op 15.jul.2024 om 14:39 schreef olcott:
> On 7/15/2024 3:35 AM, Fred. Zwarts wrote:
>> Op 15.jul.2024 om 05:35 schreef olcott:
>>> On 7/14/2024 10:02 PM, Mike Terry wrote:
>>>> On 15/07/2024 01:20, joes wrote:
>>>>> Am Sun, 14 Jul 2024 09:00:55 -0500 schrieb olcott:
>>>>>> On 7/14/2024 3:29 AM, joes wrote:
>>>>>>> Am Sat, 13 Jul 2024 18:33:53 -0500 schrieb olcott:
>>>>>>>> On 7/13/2024 6:26 PM, joes wrote:
>>>>>>>>> Can you elaborate? All runtime instances share the same static 
>>>>>>>>> code.
>>>>>>>>> I am talking about the inner HHH which is called by the simulated
>>>>>>>>> DDD. That one is, according to you, aborted. Which is wrong, 
>>>>>>>>> because
>>>>>>>>> by virtue of running the same code, the inner HHH aborts ITS
>>>>>>>>> simulation of DDD calling another HHH.
>>>>>
>>>>>>> What are the twins and what is their difference?
>>>>>>> Do you disagree with my tracing?
>>>>>
>>>>>
>>>>>> The directly executed DDD is like the first call of infinite 
>>>>>> recursion.
>>>>>> The emulated DDD is just like the second call of infinite recursion.
>>>>>> When the second call of infinite recursion is aborted then the first
>>>>>> call halts.
>>>>> Not really. Execution does not continue.
>>>>>> void Infinite_Recursion()
>>>>>> {
>>>>>>     Infinite_Recursion();
>>>>>> }
>>>>>> The above *is* infinite recursion.
>>>>>> A program could emulate the above code and simply skip line 3 causing
>>>>>> Infinite_Recursion() to halt.
>>>>> That would be incorrect.
>>>>>
>>>>>> When DDD calls HHH(DDD) HHH returns.
>>>>> Therefore it does not need to be aborted.
>>>>>> When DDD correctly emulated by HHH the call never returns as is 
>>>>>> proven
>>>>>> below. The executed DDD() has HHH(DDD) skip this call.
>>>>> I do not see this below.
>>>>>> HHH(DDD) must skip this call itself by terminating the whole DDD
>>>>>> process.
>>>>>
>>>>>> Because this HHH does not know its own machine address HHH only sees
>>>>>> that DDD calls a function that causes its first four steps to be
>>>>>> repeated. HHH does not know that this is recursive simulation. To 
>>>>>> HHH it
>>>>>> looks just like infinite recursion.
>>>>>
>>>>>> New slave_stack at:1038c4 -- create new process context for 1st DDD
>>>>>> Begin Local Halt Decider Simulation   Execution Trace Stored 
>>>>>> at:1138cc
>>>>>
>>>>>> [0000217a][001138b4][0000217f] e853f4ffff call 000015d2 ; call 
>>>>>> HHH(DDD)
>>>>>> New slave_stack at:14e2ec -- create new process context for 2nd DDD
>>>>>
>>>>>> [0000217a][0015e2dc][0000217f] e853f4ffff call 000015d2 ; call 
>>>>>> HHH(DDD)
>>>>>> Local Halt Decider: Infinite Recursion Detected Simulation Stopped
>>>>> How is this detected?
>>>>
>>>> PO seems not to want to answer you, as I notice you've asked this 
>>>> question more than once and PO dodges a direct response, so I'll 
>>>> try. (Alternatively, PO has provided a link to his source code in 
>>>> the past, so if you can find that link you can just look the answer 
>>>> yourself - the functions are all in his halt7.c file, which is 
>>>> compiled but not linked, then the obj file is interpreted within his 
>>>> x86utm.exe (source also given in the link.  The link might not 
>>>> reflect his current code??)
>>>>
>>>> Anyhow, this is what I reckon...
>>>>
>>>> HHH [outer HHH only!] examines a global trace table of simulated 
>>>> instruction (from all simulation levels merged together).  The 
>>>> particular message "Infinite Recursion Detected Simulation Stopped" 
>>>> seems to be issued when:
>>>> -  last instruction is a CALL
>>>> -  working backwards through the merged trace table, another CALL is 
>>>> encountered
>>>> -  ..which is issued at the same address
>>>> -  ..and is calling to the same address
>>>> -  ..and no "conditional branch" instructions occur in the trace table
>>>>       between the two call instructions
>>>>
>>>> KEY TO NOT BEING MISLED BY THE ABOVE:
>>>>
>>>> 0. The "Infinite Recursion Detected Simulation Stopped" message is 
>>>> just a printf.
>>>>     It does not prove that /actual/ infinite recursion was detected 
>>>> - on the contrary,
>>>>     all here but PO realise that the recursion detected is just 
>>>> finite recursion.
>>>>
>>>> 1. The trace table being examined is NOT an x86 processor trace - it 
>>>> is a
>>>>     "merged simulation trace" containing entries for ALL SIMULATION 
>>>> LEVELS.
>>>>     So the two CALL instructions are not referring to one single x86 
>>>> processor.
>>>
>>> When emulated DDD calls HHH(DDD) the outer HHH emulates itself
>>> emulating DDD.
>>>
>>> I think that joes does not understand these things.
>>>
>>>>     Typically, the last call instruction is from a deeper nested 
>>>> simulation
>>>>     than the earlier detected call instruction.  The outer 
>>>> simulations are all
>>>>     still running, but do not appear in the trace table or logs 
>>>> presented by PO
>>>>     due to the next note.
>>>>
>>>> 2. The searched trace table is filtered to only contain instructions 
>>>> within the C
>>>>     function D/DD/DDD/.. !!
>>>>     YES, YOU READ THAT RIGHT!  ALL CODE IN HHH IS TOTALLY IGNORED, 
>>>> INCLUDING
>>>>     THE CONDITIONAL BRANCH INSTRUCTIONS THAT ARE TESTING THE VERY 
>>>> ABORT TESTS
>>>>     THAT CAUSE OUTER HHH TO ABORT.
>>>>
>>>> 3. Inner HHH's do not perform the same tests as above, because they 
>>>> inspect a global
>>>>     variable which tells them they are inner HHH's.  Yeah, that 
>>>> means the simulation
>>>>     is completely broken logically... [but... the outer HHH will 
>>>> abort first, so
>>>>     PO might argue the outcome will be the same, even though 
>>>> logically it is
>>>>     broken...]
>>>>
>>>>  > Is it also triggered when calling a function
>>>>  > in a loop?
>>>>
>>>> Not sure what you mean.  Calling a function in a loop ends if the 
>>>> loop ends, right?  What loop are you thinking of?
>>>>
>>>> Anyhow, provided the call instructions are physically located in 
>>>> function D() [i.e. not H() or something called from H] I guess it 
>>>> would match.  But the C function D has only one call instruction, 
>>>> which isn't in a loop!
>>>>
>>>> Regards,
>>>> Mike.
>>>>
>>>
>>> *I have boiled it all down to this simple tautology*
>>> 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.
>>>
>>>
>> But since HHH aborts, 
> 
> The above tautology asks about the behavior of DDD correctly
> emulated by pure function HHH according to the semantics
========== REMAINDER OF ARTICLE TRUNCATED ==========