Path: ...!local-2.nntp.ord.giganews.com!Xl.tags.giganews.com!local-1.nntp.ord.giganews.com!nntp.brightview.co.uk!news.brightview.co.uk.POSTED!not-for-mail
NNTP-Posting-Date: Mon, 15 Jul 2024 03:02:16 +0000
Subject: Re: DDD correctly emulated by HHH is Correctly rejected as
 non-halting V2
Newsgroups: comp.theory
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>
From: Mike Terry <news.dead.person.stones@darjeeling.plus.com>
Date: Mon, 15 Jul 2024 04:02:15 +0100
User-Agent: Mozilla/5.0 (Windows NT 10.0; Win64; x64; rv:91.0) Gecko/20100101
 Firefox/91.0 SeaMonkey/2.53.17
MIME-Version: 1.0
In-Reply-To: <8a6e6d9ff49aabe2525ce5729a439c807de4768a@i2pn2.org>
Content-Type: text/plain; charset=windows-1252; format=flowed
Content-Transfer-Encoding: 7bit
Message-ID: <34Ocnd4voeWlDAn7nZ2dnZfqnPudnZ2d@brightview.co.uk>
Lines: 109
X-Usenet-Provider: http://www.giganews.com
X-Trace: sv3-xZrdQmKppEv/mNG3KmVcBhh1RMyEnJ10ZSwV8g9eyqXzwGpj+KVSxQfVDocI07OCy1XM7y8oqcjNPjD!UZhPIMqUHHVGyJIi2JlVCsGvFYOxr6n40t/tCEKcW6gF2i/PFHcJMZSGRIq66OZeXG2PnZfyHPLL!s9UXWt4Id//iDjA/wuo/+Gnj0u6G
X-Abuse-and-DMCA-Info: Please be sure to forward a copy of ALL headers
X-Abuse-and-DMCA-Info: Otherwise we will be unable to process your complaint properly
X-Postfilter: 1.3.40
Bytes: 7151

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.
    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.