Path: ...!news.nobody.at!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: HHH(DDD) sees the exact same behavior pattern as
 HHH(Infinite_Recursion)
Date: Sun, 28 Jul 2024 20:59:40 +0200
Organization: A noiseless patient Spider
Lines: 129
Message-ID: <v864et$2409$1@dont-email.me>
References: <v85kp7$3v9fb$3@dont-email.me>
MIME-Version: 1.0
Content-Type: text/plain; charset=UTF-8; format=flowed
Content-Transfer-Encoding: 8bit
Injection-Date: Sun, 28 Jul 2024 20:59:42 +0200 (CEST)
Injection-Info: dont-email.me; posting-host="e64eb462ef708caff68e0f4da777a1db";
	logging-data="69641"; mail-complaints-to="abuse@eternal-september.org";	posting-account="U2FsdGVkX186xQv2ehYvmTpkOhLG12Zg"
User-Agent: Mozilla Thunderbird
Cancel-Lock: sha1:xit0JMiAU7vXtZoCZhJbtJNiuPg=
In-Reply-To: <v85kp7$3v9fb$3@dont-email.me>
Content-Language: en-GB
Bytes: 6453

Op 28.jul.2024 om 16:32 schreef olcott:
> It is ridiculously stupid to expect the correct emulation
> of a non-halting input to end.

It is also ridiculous to expect that a halting program must be aborted 
to prevent non-termination.

> 
> HHH(DDD) is the exact same pattern with Infinite_Recursion()
> where there are no conditional branch instructions that would
> prevent the first three instructions of Infinite_Recursion()
> from endlessly repeating.
> 
> void Infinite_Recursion()
> {
>    Infinite_Recursion();
> }
> 


HHH has the same pattern as

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

Both HHH and Finite_Recursion halt after a few recursions.
That is because of the conditional branch instructions within HHH, when 
HHH simulates itself, as part of the input.

> _Infinite_Recursion()
> [0000215a] 55         push ebp      ; 1st line
> [0000215b] 8bec       mov ebp,esp   ; 2nd line
> [0000215d] e8f8ffffff call 0000215a ; 3rd line
> [00002162] 5d         pop ebp
> [00002163] c3         ret
> Size in bytes:(0010) [00002163]
> 
> Begin Local Halt Decider Simulation   Execution Trace Stored at:113934
> [0000215a][00113924][00113928] 55         push ebp      ; 1st line
> [0000215b][00113924][00113928] 8bec       mov ebp,esp   ; 2nd line
> [0000215d][00113920][00002162] e8f8ffffff call 0000215a ; 3rd line
> [0000215a][0011391c][00113924] 55         push ebp      ; 1st line
> [0000215b][0011391c][00113924] 8bec       mov ebp,esp   ; 2nd line
> [0000215d][00113918][00002162] e8f8ffffff call 0000215a ; 3rd line
> Local Halt Decider: Infinite Recursion Detected Simulation Stopped
> 
> If you cannot see that the above x86 machine code proves that
> it will never halt then you can't possibly understand what I
> have been saying.
> 
> The first three lines of _Infinite_Recursion() repeat and there
> are no conditional branch in that sequence that can possibly keep
> it from repeating forever.
> 
> HHH(DDD) is the exact same pattern is shown below. The first
> four lines of DDD repeat and there are are no conditional branch
> in that sequence that can possibly keep it from repeating forever.

HHH has a very different pattern, because of the conditional branch 
instructions in the input, namely, those in HHH itself.
HHH halts, as is shown by the direct execution and by a correct simulation.

> 
> =====
> 
> void DDD()
> {
>    HHH(DDD);
> }

DDD is a misleading and unneeded complication. 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.
It shows that HHH cannot possibly simulate itself correctly.

> 
> _DDD()
> [00002177] 55               push ebp      ; 1st line
> [00002178] 8bec             mov ebp,esp   ; 2nd line
> [0000217a] 6877210000       push 00002177 ; push DDD
> [0000217f] e853f4ffff       call 000015d7 ; call HHH
> [00002184] 83c404           add esp,+04
> [00002187] 5d               pop ebp
> [00002188] c3               ret
> Size in bytes:(0018) [00002188]
> 
> // executed HHH emulates 1st instance of DDD
> New slave_stack at:10388d
> Begin Local Halt Decider Simulation   Execution Trace Stored at:113895
> [00002177][00113885][00113889] 55         push ebp      ; 1st line
> [00002178][00113885][00113889] 8bec       mov ebp,esp   ; 2nd line
> [0000217a][00113881][00002177] 6877210000 push 00002177 ; push DDD
> [0000217f][0011387d][00002184] e853f4ffff call 000015d7 ; call HHH
> 
> // emulated HHH emulates 2nd instance of DDD
> New slave_stack at:14e2b5
> [00002177][0015e2ad][0015e2b1] 55         push ebp      ; 1st line
> [00002178][0015e2ad][0015e2b1] 8bec       mov ebp,esp   ; 2nd line
> [0000217a][0015e2a9][00002177] 6877210000 push 00002177 ; push DDD
> [0000217f][0015e2a5][00002184] e853f4ffff call 000015d7 ; call HHH
> Local Halt Decider: Infinite Recursion Detected Simulation Stopped
> 

HHH is programmed to print an incorrect message after two recursion. 
Apparently the programmer thought that two recursions is enough to prove 
an infinite recursion. But two differs from infinite.
One cycle later the simulated HHH would abort and halt, after which DDD 
would halt, too.
But olcott is dreaming of a non-aborting non-halting version of HHH and 
thinks that dreams are a correct substitute for logic.

No matter how much olcott wants it to be correct, or how many times 
olcott repeats that it is correct, it does not change the fact that such 
a simulation is incorrect, because it is unable to reach the end.
Olcott's own claim that the simulated HHH does not reach its end 
confirms it. The trace he has shown also proves that HHH cannot reach 
the end of its own simulation. So, his own claims prove that it is true 
that HHH cannot possibly simulate itself up to the end, which makes the 
simulation incomplete and, therefore, incorrect.

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