Path: ...!weretis.net!feeder9.news.weretis.net!news.nk.ca!rocksolid2!i2pn2.org!.POSTED!not-for-mail
From: Richard Damon <richard@damon-family.org>
Newsgroups: comp.theory
Subject: Re: DDD incorrectly emulated by HHH is INCorrectly rejected as
 non-halting V2 --- key point needing review
Date: Mon, 15 Jul 2024 22:19:10 -0400
Organization: i2pn2 (i2pn.org)
Message-ID: <f68e6c2302f53b2b44e0e494f93f2326e2d4f8d5@i2pn2.org>
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>
 <aa7643b6d8c46d2c4dd5ef92ae3650afe114adbb@i2pn2.org>
 <M0SdnQhovsrX1Qj7nZ2dnZfqnPGdnZ2d@brightview.co.uk>
 <v73iei$os5d$1@dont-email.me>
MIME-Version: 1.0
Content-Type: text/plain; charset=UTF-8; format=flowed
Content-Transfer-Encoding: 8bit
Injection-Date: Tue, 16 Jul 2024 02:19:10 -0000 (UTC)
Injection-Info: i2pn2.org;
	logging-data="3273011"; mail-complaints-to="usenet@i2pn2.org";
	posting-account="diqKR1lalukngNWEqoq9/uFtbkm5U+w3w6FQ0yesrXg";
User-Agent: Mozilla Thunderbird
Content-Language: en-US
X-Spam-Checker-Version: SpamAssassin 4.0.0
In-Reply-To: <v73iei$os5d$1@dont-email.me>
Bytes: 7649
Lines: 118

On 7/15/24 12:23 PM, olcott wrote:
> On 7/15/2024 11:03 AM, Mike Terry wrote:
>> On 15/07/2024 09:59, joes wrote:
>>> Am Sun, 14 Jul 2024 22:35:03 -0500 schrieb 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:
>>>
>>>>>>> [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??)
>>> Thank you. I didn't bother digging through their code, and they refused
>>> to give the abortion criterion.
>>>
>>>>> 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...]
>>> Ah, and here I believed them when they said they had rewritten it.
>>
>> I doubt he has done it properly if at all.  I.e. I'm confident there 
>> will still be mutable static data giving different code paths for 
>> outer/inner executions.
>>
> 
> That is counter-factual.
> 
>> I offered to help PO sort out the required recursive logic but this 
>> was ignored, PO saying it would take him thousands of years(?) to do 
>> it correctly.  I reckon anyone else here would fix it in a couple of 
>> hours!
>>
> 
> *THIS IS THE KEY POINT NEEDING MIKES REVIEW*
> I propose that the use of static local variables to
> pass information up from the slaves to the master
> does not violate computability.
> 

But the inner one CAN NOT KNOW it is an inner one without violating the 
constraint.

Now, all this seems to be an attempt to make it so the decider can know 
that it is seeing a copy of itself, but once it knows that, then the 
necessary condition that whatever the outer one does must be compatible 
with what it has decided the inner one will do applies, or you are just 
admitting that it did incorrect logic on the determination of the 
behavior of the inner one. Remember also, just because the outer 
simulator aborts the inner doesn't mean the behavior of the program 
represented by the input stopped progressing, as ALL copies of it do the 
same thing, and continue in their behavior till they reach their end.

And of course, the REAL problem is figuring out how every HHH can return 
to main but not to DDD, which means that it CAN'T be a pure function, as 
that violates the requirement. This is because BY DEFINITION, the 
"behavior of the input" is the actual behavior of the program that it 
represents, and NOT the results of the PARTIAL emulation done by the HHH 
that returned the answer.