Re: The execution trace of HHH1(DDD) shows the divergence

On 6/11/2025 4:06 PM, anthk wrote:

On 2025-06-07, olcott <polcott333@gmail.com> wrote:

The execution trace of HHH1(DDD) shows the divergence
of DDD emulated by HHH from DDD emulated by HHH1.
>
int main()
{
    HHH1(DDD);
}
>
Shows that DDD emulated by HHH and DDD emulated by
HHH1 diverges as soon as HHH begins emulating itself
emulating DDD.
>
*From the execution trace of HHH1(DDD) shown below*
DDD emulated by HHH1              DDD emulated by HHH
[00002183] push ebp               [00002183] push ebp
[00002184] mov ebp,esp            [00002184] mov ebp,esp
[00002186] push 00002183 ; DDD    [00002186] push 00002183 ; DDD
[0000218b] call 000015c3 ; HHH    [0000218b] call 000015c3 ; HHH
*HHH1 emulates DDD once then HHH emulates DDD once, these match*
>
The next instruction of DDD that HHH emulates is at
the machine address of 00002183.
>
The next instruction of DDD that HHH1 emulates is at
the machine address of 00002190.
>
00002183 != 00002190
>
_DDD()
[00002183] 55             push ebp
[00002184] 8bec           mov ebp,esp
[00002186] 6883210000     push 00002183 ; push DDD
[0000218b] e833f4ffff     call 000015c3 ; call HHH
[00002190] 83c404         add esp,+04
[00002193] 5d             pop ebp
[00002194] c3             ret
Size in bytes:(0018) [00002194]
>
_main()
[000021a3] 55             push ebp
[000021a4] 8bec           mov ebp,esp
[000021a6] 6883210000     push 00002183 ; push DDD
[000021ab] e843f3ffff     call 000014f3 ; call HHH1
[000021b0] 83c404         add esp,+04
[000021b3] 33c0           xor eax,eax
[000021b5] 5d             pop ebp
[000021b6] c3             ret
Size in bytes:(0020) [000021b6]
>
   machine   stack     stack     machine    assembly
   address   address   data      code       language
  ========  ========  ========  ========== =============
<main is executed>
[000021a3][0010382d][00000000] 55         push ebp      ; main()
[000021a4][0010382d][00000000] 8bec       mov ebp,esp   ; main()
[000021a6][00103829][00002183] 6883210000 push 00002183 ; push DDD
[000021ab][00103825][000021b0] e843f3ffff call 000014f3 ; call HHH1
</main is executed>
>
New slave_stack at:1038d1
Begin Local Halt Decider Simulation   Execution Trace Stored at:1138d9
>
<DDD emulated by HHH1>
[00002183][001138c9][001138cd] 55         push ebp      ; DDD of HHH1
[00002184][001138c9][001138cd] 8bec       mov ebp,esp   ; DDD of HHH1
[00002186][001138c5][00002183] 6883210000 push 00002183 ; push DDD
[0000218b][001138c1][00002190] e833f4ffff call 000015c3 ; call HHH
</DDD emulated by HHH1>
>
New slave_stack at:14e2f9
Begin Local Halt Decider Simulation   Execution Trace Stored at:15e301
>
<DDD emulated by HHH>
[00002183][0015e2f1][0015e2f5] 55         push ebp      ; DDD of HHH[0]
[00002184][0015e2f1][0015e2f5] 8bec       mov ebp,esp   ; DDD of HHH[0]
[00002186][0015e2ed][00002183] 6883210000 push 00002183 ; push DDD
[0000218b][0015e2e9][00002190] e833f4ffff call 000015c3 ; call HHH
<DDD emulated by HHH>
>
New slave_stack at:198d21  DDD emulated by HHH
*This is the beginning of the divergence of the behavior*
*HHH is emulating itself emulating DDD, HHH1 never does that*
>
<DDD emulated by HHH emulating itself>
[00002183][001a8d19][001a8d1d] 55         push ebp      ; DDD of HHH[1]
[00002184][001a8d19][001a8d1d] 8bec       mov ebp,esp   ; DDD of HHH[1]
[00002186][001a8d15][00002183] 6883210000 push 00002183 ; push DDD
[0000218b][001a8d11][00002190] e833f4ffff call 000015c3 ; call HHH
</DDD emulated by HHH emulating itself>
>
Local Halt Decider: Infinite Recursion Detected Simulation Stopped
HHH returns to caller
>
<DDD emulated by HHH1>
[00002190][001138c9][001138cd] 83c404     add esp,+04 ; DDD of HHH1
[00002193][001138cd][000015a8] 5d         pop ebp     ; DDD of HHH1
[00002194][001138d1][0003a980] c3         ret         ; DDD of HHH1
</DDD emulated by HHH1>
>
<main is executed>
[000021b0][0010382d][00000000] 83c404     add esp,+04 ; main()
[000021b3][0010382d][00000000] 33c0       xor eax,eax ; main()
[000021b5][00103831][00000018] 5d         pop ebp     ; main()
[000021b6][00103835][00000000] c3         ret         ; main()
</main is executed>
Number of Instructions Executed(352831) == 5266 Pages
>

 Lean Lisp first, ideally with Scheme. Go get Concrete Abstractions
and learn about recursivity and taill call optimization.

Tail optimization would at best convert recursive emulation
into an infinite loop.
void DDD()
{
   HHH(DDD);
   return;
}
DDD correctly emulated by HHH cannot possibly reach its
own "return" statement final halt state, thus is correctly
rejected by HHH as non-halting.
int DD()
{
   int Halt_Status = HHH(DD);
   if (Halt_Status)
     HERE: goto HERE;
   return Halt_Status;
}
The point of all of this is that the halting problem's
counter-example input is also correctly rejected as
non-halting thus refuting the conventional HP proof.
--
Copyright 2025 Olcott "Talent hits a target no one else can hit; Genius
hits a target no one else can see." Arthur Schopenhauer