Re: Simulation vs. Execution in the Halting Problem

On 01/06/2025 05:01, olcott wrote:

On 5/31/2025 10:32 PM, Mike Terry wrote:

On 01/06/2025 02:31, olcott wrote:

On 5/31/2025 7:44 PM, Mike Terry wrote:

On 01/06/2025 01:18, olcott wrote:

[..snip..]

>
We cannot do a separate side-by-side execution trace of
HHH(DDD) and HHH1(DDD) because the DDD simulated by HHH1
calls HHH(DDD) as a part of this same simulation.

>
Duh!  The DDD simulated by HHH ALSO calls HHH(DDD) as a part of the same simulation.
>
They BOTH call HHH(DDD) as part of the simulation.  Duuuuuh....
>
I've presented the two traces to you side by side on more than one occasion.  Do you really have no recollection of that?  Your explanation of why we supposedly can't put them side by side is literally gibberish!
>

>
 From the trace shown below we can see that HHH simulates
DDD one whole execution trace more than HHH1 does.

>
Really?  That's not at all what I see - but perhaps you can explain what you're saying.
>
Mark on the trace below where you think HHH1's simulation [i.e. the simulation /performed/ by HHH1] starts and ends.  Also mark where you think HHH's simulation starts and ends.
>
Then to save me the trouble, try to put them side by side to see if they match up...
>
>
Mike.
>

>
I really appreciate your sincere honesty and the great
diligence that you have shown evaluating my work. No
one else on the planet has put nearly the same effort
as you in carefully evaluating the key details of my work.
>

There is a terminology issue here to resolve.
If A simulates B and B simulates C, what should a "trace" of A's simulation look like?
a)   it includes both B's and C's instructions, interlaced.
b)   it is just B's instructions.
Both of those would be valid ways of looking at things.
(a) is more in line with how you typically present traces, and in your code A's view of the simulations includes both B's and C's instructions - it needs to be that way for your so-called "infinite recursive emulation" test to make sense.
(b) is ok too, as long as consistency is maintained.
The claim you are disputing is "HHH1's and HHH's simulation of DDD exactly match up to the point where HHH aborts".  More generally, any two (partial) simulations of any program will match, up to the earliest step where one of the simulations is aborted.  Definition (b) is "weaker" than (a), in that if (a) is understood, and the two simulations match under this definition, then it is obvious that under definition (b) the simulations will still match, because (b) is just some filtered version of (a).
So I'll pause here until you say which of (a) (b) you think characterises simulations matching or not matching.
Mike.

>

>
*It is only after this whole extra recursive emulation*
*divergence that HHH aborts its emulated DDD*
>
_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
  ========  ========  ========  ========== =============
[000021a3][0010382d][00000000] 55         push ebp
[000021a4][0010382d][00000000] 8bec       mov ebp,esp
[000021a6][00103829][00002183] 6883210000 push 00002183 ; push DDD
[000021ab][00103825][000021b0] e843f3ffff call 000014f3 ; call HHH1
New slave_stack at:1038d1
>

>
HHH1 begins its simulation of DDD.

>
Right.  Below I'm going to use notation [n] on occasions to make clear which level of simulation is doing things.  So e.g. HHH1[0] is HHH1 directly executed.  HHH[1] is HHH simulated by HHH1 and so on.
>

 DDD simulated by HHH1[0]
 

>

Begin Local Halt Decider Simulation   Execution Trace Stored at:1138d9
[00002183][001138c9][001138cd] 55         push ebp
[00002184][001138c9][001138cd] 8bec       mov ebp,esp
[00002186][001138c5][00002183] 6883210000 push 00002183 ; push DDD
[0000218b][001138c1][00002190] e833f4ffff call 000015c3 ; call HHH
New slave_stack at:14e2f9
>

>
HHH begins its simulation of DDD

>
Right.  The following are part of both HHH1[0]'s and HHH[1]'s simulations...
>

 No. This is DDD simulated by HHH[1]
 

>

Begin Local Halt Decider Simulation   Execution Trace Stored at:15e301
[00002183][0015e2f1][0015e2f5] 55         push ebp
[00002184][0015e2f1][0015e2f5] 8bec       mov ebp,esp
[00002186][0015e2ed][00002183] 6883210000 push 00002183 ; push DDD
[0000218b][0015e2e9][00002190] e833f4ffff call 000015c3 ; call HHH

>
HHH simulates itself simulating DDD

>
Right.  The following are part of HHH1[0]'s and HHH[1]'s and HHH[2]'s simulations...
>

 No this is DDD simulated by HHH[2]
 

>

New slave_stack at:198d21
[00002183][001a8d19][001a8d1d] 55         push ebp
[00002184][001a8d19][001a8d1d] 8bec       mov ebp,esp
[00002186][001a8d15][00002183] 6883210000 push 00002183 ; push DDD
[0000218b][001a8d11][00002190] e833f4ffff call 000015c3 ; call HHH
Local Halt Decider: Infinite Recursion Detected Simulation Stopped
>

>
HHH aborts its simulation of DDD.

>

 HHH[1] aborts its simulation of DDD. This aborted
simulation includes HHH simulating itself simulating
DDD AKA HHH[2].
 returns to its caller: DDD simulated by HHH1[0]
 

Right.  HHH[1] has abandoned simulation [2] (and nested simulation [3]).
This is the end of HHH[1]'s simulation, but HHH1[0]'s simulation continues...
>

HHH1 simulates the rest of its own DDD.

>
You mean the rest of HHH[1]'s DDD.  (HHH[1] is still being simulated)
>

 No this is HHH1[0] finishing its one and only simulation of DDD.
 

>

[00002190][001138c9][001138cd] 83c404     add esp,+04
[00002193][001138cd][000015a8] 5d         pop ebp
[00002194][001138d1][0003a980] c3         ret

>

>
And this is where HHH1's simulation ends.
(Below is directly executed code...)
>

return to main()

[000021b0][0010382d][00000000] 83c404     add esp,+04
[000021b3][0010382d][00000000] 33c0       xor eax,eax
[000021b5][00103831][00000018] 5d         pop ebp
[000021b6][00103835][00000000] c3         ret
Number of Instructions Executed(352831) == 5266 Pages
>
>

>

>
So now, you need to collect up the trace entries which are part of HHH1's simulation (and nested simulations), and HHH[1]'s simulation (and nested simulations).  That's just looking at where the respective traces start and end above.
>

 No all that you need to see is that HHH simulates DDD twice
(thus already diverging from DDD simulated by HHH1)
before HHH aborts its simulation of DDD.
 

Here, I can do that:
>
-------------- HHH1[0] simulation (+nested simulations) ----------------
  machine   stack     stack     machine    assembly
  address   address   data      code       language
  ========  ========  ========  ========== =============
[00002183][001138c9][001138cd] 55         push ebp
[00002184][001138c9][001138cd] 8bec       mov ebp,esp
[00002186][001138c5][00002183] 6883210000 push 00002183 ; push DDD
[0000218b][001138c1][00002190] e833f4ffff call 000015c3 ; call HHH
[00002183][0015e2f1][0015e2f5] 55         push ebp
[00002184][0015e2f1][0015e2f5] 8bec       mov ebp,esp
[00002186][0015e2ed][00002183] 6883210000 push 00002183 ; push DDD
[0000218b][0015e2e9][00002190] e833f4ffff call 000015c3 ; call HHH
### hint: this is where HHH aborts, but HHH1 continues the simulation! :)
[00002183][001a8d19][001a8d1d] 55         push ebp
[00002184][001a8d19][001a8d1d] 8bec       mov ebp,esp
[00002186][001a8d15][00002183] 6883210000 push 00002183 ; push DDD
[0000218b][001a8d11][00002190] e833f4ffff call 000015c3 ; call HHH
[00002190][001138c9][001138cd] 83c404     add esp,+04
[00002193][001138cd][000015a8] 5d         pop ebp
[00002194][001138d1][0003a980] c3         ret
[trace ended by DDD[1] returning normally]
>
>
-------------- HHH[1] simulation (+nested simulations) ----------------
  machine   stack     stack     machine    assembly
  address   address   data      code       language
  ========  ========  ========  ========== =============
[00002183][0015e2f1][0015e2f5] 55         push ebp
[00002184][0015e2f1][0015e2f5] 8bec       mov ebp,esp
[00002186][0015e2ed][00002183] 6883210000 push 00002183 ; push DDD
[0000218b][0015e2e9][00002190] e833f4ffff call 000015c3 ; call HHH
[00002183][001a8d19][001a8d1d] 55         push ebp
[00002184][001a8d19][001a8d1d] 8bec       mov ebp,esp
[00002186][001a8d15][00002183] 6883210000 push 00002183 ; push DDD
[0000218b][001a8d11][00002190] e833f4ffff call 000015c3 ; call HHH
[trace ended by HHH[1] aborting]
>
>
So do you agree that those are the right entries?  (They are just the entries you identified above, between the beginning and ends of the respective simulations.)
>

 *I am not going to look at them*
HHH emulates DDD twice before it aborts thus
the abort is not the cause of the divergence.
 The moment that HHH[2] begins emulating DDD
DDD emulated by HHH1 and DDD emulated by HHH diverge.
 

Now you will be in a position to do the side-by-side comparison you said wasn't possible!  You need to, um, put the two traces above side by side!
>
OK, clearly we are not going to exactly match on stack addresses or stack data, but these are not unique attributes of the computation, as Allocate() will assign different storage addresses for each simulation. What we want is for machine addresses, machine code and assemply language to match or not UP TO THE POINT WHERE HHH[1] ABORTS.
>
>
Mike.
>