Re: Overview of proof that the input to HHH(DDD) specifies non-halting behavior --- Mike --- in our head

Op 14.aug.2024 om 15:56 schreef olcott:

On 8/14/2024 4:01 AM, Fred. Zwarts wrote:

Op 13.aug.2024 om 21:20 schreef olcott:

>
A simulation of N instructions of DDD by HHH according to
the semantics of the x86 language is necessarily correct.

We can agree that HHH made a good start for the simulation with a correct simulation of the first N steps, but failed to complete the simulation by not reaching the end of the simulation.
>

 No wrong. That N instructions were emulating correctly
is the whole point. Anything else is a distraction from
this point.

No, you are trying to twist the meaning of the words. Simulating a few instructions is not a correct simulation of a program.

 

Note that the semantics of the x86 language does not depend on who or what is using it. The direct execution uses the same semantics and it correctly shows that the end of the program can be reached according to this semantics. So, when the simulator does not reach the end, it deviates from the semantics of the input, when it processes the same input.

 _DDD()
[00002172] 55         push ebp      ; housekeeping
[00002173] 8bec       mov ebp,esp   ; housekeeping
[00002175] 6872210000 push 00002172 ; push DDD
[0000217a] e853f4ffff call 000015d2 ; call HHH(DDD)
[0000217f] 83c404     add esp,+04
[00002182] 5d         pop ebp
[00002183] c3         ret
Size in bytes:(0018) [00002183]
 The is a hypothetical mental exercise and can be
accomplished even if the only DDD in the world
was simply typed into a word processor and never run.
 HHH can be purely imaginary yet must emulate the
above code and itself according to the semantics
of the x86 language. In this case HHH is a pure
emulator.
 (a) On this basis we know that such an HHH would
emulate the first four instructions of DDD.
 (b) This includes a calls from the emulated DDD
to an emulated HHH(DDD).
 (c) This emulated HHH would emulate the first
four instructions of DDD.
 (b) and (c) keep repeating.
 We can do that all in our head never needing
any actually existing HHH.
 

Indeed, the HHH that is a pure simulator that does not abort, does not halt. But it is incorrect to say that it simulates only the first four instructions of DDD. If it is a correct simulator, then it will also simulate the instructions in the called HHH.
But this is all a change of subject and distraction from the subject because we were talking about the HHH that halts, which can only be the case if it aborts.
The HHH that does not abort should now disappear from your head and we now look only at the HHH that aborts and halts.
For this HHH it is not true that '(b) and (c) keep repeating', because it aborts after N cycles.
That is something we can do in our head, too.
We see that when HHH aborts after N cycles, the simulated HHH has only performed N-1 cycles. The simulated HHH has the same code as the simulating HHH and, therefore, has the same behaviour. Both the simulating and the simulated HHH are coded to abort after N cycles. So, we can see in our head that the simulated HHH would also abort after N cycles, but it was aborted prematurely, when it was only 1 cycle from the end.
This makes that the simulation is incomplete and, therefore, incorrect.