Re: HHH(Infinite_Recursion) and HHH(DDD) derive same non-halting execution trace

Liste des GroupesRevenir à c theory 
Sujet : Re: HHH(Infinite_Recursion) and HHH(DDD) derive same non-halting execution trace
De : F.Zwarts (at) *nospam* HetNet.nl (Fred. Zwarts)
Groupes : comp.theory
Date : 29. Jul 2024, 20:25:06
Autres entêtes
Organisation : A noiseless patient Spider
Message-ID : <v88qaj$ju20$2@dont-email.me>
References : 1 2 3 4 5 6 7
User-Agent : Mozilla Thunderbird
Op 29.jul.2024 om 18:43 schreef olcott:
On 7/28/2024 3:57 AM, Mikko wrote:
On 2024-07-27 19:27:16 +0000, olcott said:
>
It is a verified fact that HHH get the correct halt
status decision in that HHH exactly matched that same
behavior pattern as this:
>
No, it is not a verified fact. It is obvious from the code of DDD
that DDD halts if HHH does, and otherwise HHH does not answer.
Therefore, if HHH answers, the correct answer is "halts".
>
 HHH(Infinite_Recursion) and HHH(DDD) derive equivalent
non-halting behavior patterns in the execution trace of
their 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]
 *Infinite_Recursion correctly emulated by HHH*
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
*Repeat first 3 lines with no conditional branch to prevent repeats*
  _DDD()
[00002163] 55         push ebp      ; housekeeping
[00002164] 8bec       mov ebp,esp   ; housekeeping
[00002166] 6863210000 push 00002163 ; push DDD
[0000216b] e853f4ffff call 000015c3 ; call HHH(DDD)
[00002170] 83c404     add esp,+04
[00002173] 5d         pop ebp
[00002174] c3         ret
Size in bytes:(0018) [00002174]
 *DDD correctly emulated by HHH*
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
Olcott cheats by hiding that a correct simulation of the call instruction, according to the semantics of the x86 language, continues to simulate the instructions of HHH, which has conditional branch instructions.

[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
Again, Olcotts cheat by hiding that a correct simulation of the call instruction, according to the semantics of the x86 language, continues to simulate the instructions of HHH, which has conditional branch instructions.

Local Halt Decider: Infinite Recursion Detected Simulation Stopped
*Repeat first 4 lines with no conditional branch to prevent repeats*
Ignoring the conditional branch instruction is a severe deviation from the semantics of the semantics of the x86 language. So, olcott's own criterion tells us that the simulation is incorrect.
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.
Sipser would agree that this incorrect simulation cannot be used to detect a non-halting behaviour.

Date Sujet#  Auteur
7 Jul 25 o 

Haut de la page

Les messages affichés proviennent d'usenet.

NewsPortal