Path: ...!news.mixmin.net!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:12:20 +0200
Organization: A noiseless patient Spider
Lines: 128
Message-ID: <v73sak$qkp2$3@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>
 <v71qj3$bvm2$2@dont-email.me>
 <3d124d535f6d59565df213fa58242ee156ee96bb@i2pn2.org>
 <v7349r$mjis$1@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:12:21 +0200 (CEST)
Injection-Info: dont-email.me; posting-host="11cf5ed0512e2277f3e9eeb7013e4f25";
	logging-data="873250"; mail-complaints-to="abuse@eternal-september.org";	posting-account="U2FsdGVkX18840eC0f6JPt3N9mU102b8"
User-Agent: Mozilla Thunderbird
Cancel-Lock: sha1:1GKl3QaXBHgdOyAHqGtQ6Ler0cU=
Content-Language: en-GB
In-Reply-To: <v7349r$mjis$1@dont-email.me>
Bytes: 7485

Op 15.jul.2024 om 14:22 schreef olcott:
> On 7/15/2024 3:49 AM, joes wrote:
>> Am Sun, 14 Jul 2024 19:30:27 -0500 schrieb olcott:
>>> On 7/14/2024 7:20 PM, 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? Is it also triggered when calling a function in a
>>>> loop?
>>
>>> You never bothered to answer whether or not you have 100% understanding
>>> of infinite recursion. If you don't then you can never understand what I
>>> am saying. If you do that I already proved my point. Here is the proof
>>> again:
>> As if you would believe me.
>> You never bothered to answer my questions (see above).
>> That only proves that HHH and DDD halt.
>>
> 
> This *is* an answer too difficult for you to understand.
> 
> New slave_stack at:1038c4
> Begin Local Halt Decider Simulation   Execution Trace Stored at:1138cc
> [00002172][001138bc][001138c0] 55         push ebp      ; housekeeping
> [00002173][001138bc][001138c0] 8bec       mov ebp,esp   ; housekeeping
> [00002175][001138b8][00002172] 6872210000 push 00002172 ; push DDD
> [0000217a][001138b4][0000217f] e853f4ffff call 000015d2 ; call HHH(DDD)
> New slave_stack at:14e2ec
> [00002172][0015e2e4][0015e2e8] 55         push ebp      ; housekeeping
> [00002173][0015e2e4][0015e2e8] 8bec       mov ebp,esp   ; housekeeping
> [00002175][0015e2e0][00002172] 6872210000 push 00002172 ; push DDD
> [0000217a][0015e2dc][0000217f] e853f4ffff call 000015d2 ; call HHH(DDD)
> Local Halt Decider: Infinite Recursion Detected Simulation Stopped
> 

A clear proof of an incorrect simulation, because there was no infinite 
recursion. Only N recursions, which were aborted after N-1 recursions, 
so the simulation skipped an important part of the input, which made it 
invalid.

In fact, DDD has nothing to do with it. It is easy to eliminate DDD:

        int main() {
          return HHH(main);
        }

This has the same problem. This proves that the problem is not in DDD, 
but in HHH, which halts when it aborts the simulation, but it decides 
that the simulation of itself does not halt.

HHH is unable to decide about finite recursions.

void Finite_Recursion (int N) {
   if (N > 0) Finite_Recursion (N - 1);
}

It decides after N recursions that there is an infinite recursion, which 
is incorrect.

Your HHH is programmed to abort the simulation after N cycles of 
recursive simulations. Therefore, it is incorrect to abort the 
simulation of HHH when the simulated HHH has performed N-1 cycles, 
because that changes the behaviour of HHH.
Since the simulated HHH always runs one cycle behind the simulating HHH, 
it is clear that HHH can never simulate enough cycles for a correct 
simulation, as is required by the x86 language.
Therefore, the simulation is incorrect according to the criteria you 
stipulated.
The conclusion is simple:
HHH cannot possibly simulate itself correctly.

No matter how much you want it to be correct, or how many times you 
repeat that it is correct, it does not change the fact that such a 
simulation is incorrect, because it is unable to reach the end.

Sipser would agree that this incorrect simulation cannot be used to 
detect a non-halting behaviour.