XPost: comp.theory, sci.logic, sci.math
On 6/2/22 1:26 AM, olcott wrote:
It is dead obvious that the simulated input to H(P,P) never reaches
its "ret" instruction
It is clear that the simulation *BY H* can never reach that instructions.
A *CORRECT* Simulation of that input by a "UTM" will reach that "ret" instruction if H(P,P) returns 0.
It is completely obvious that when H(P,P) correctly emulates its input
that it must emulate the first seven instructions of P. Because the
seventh instruction repeats this process we can know with complete
certainty that the emulated P never reaches its find “ret” instruction, thus never halts.
That is your error, you don't understand what the 7th instruction does.
A Call instruction pushes the return address and then continues the
execution at the address specified. Thus, the next instuction executed
will be the first instuction of the subroutine H, which is part of the
program P.
You trace doesn't show that.
That is why your logic is incorrect.
The key is to realize that your logic is based on the FALSEHOOD that the
H called by P will just unconditionally simulate the code provided,
while at the same time, the IDENTICAL simulator will abort its copy of
that simulation.
If H can recognize that the execution path has entered a copy of itself,
and generates an altered trace based on that fact, it MUST, to get a
correct analysis, take into account ALL of the properties of H, in
particular for this case, that this H will abort its simulation of its
input and return 0 (at least as you have currently defined it).
You H is currently incorrect because it sees that there is a copy of
itself, but it makes an known incorrect assumption of the behavior of
that copy.
_P()
[00001352](01) 55 push ebp
[00001353](02) 8bec mov ebp,esp
[00001355](03) 8b4508 mov eax,[ebp+08]
[00001358](01) 50 push eax // push P [00001359](03) 8b4d08 mov ecx,[ebp+08]
[0000135c](01) 51 push ecx // push P [0000135d](05) e840feffff call 000011a2 // call H [00001362](03) 83c408 add esp,+08
[00001365](02) 85c0 test eax,eax
[00001367](02) 7402 jz 0000136b
[00001369](02) ebfe jmp 00001369
[0000136b](01) 5d pop ebp
[0000136c](01) c3 ret
Size in bytes:(0027) [0000136c]
Begin Local Halt Decider Simulation Execution Trace Stored at:212352
machine stack stack machine assembly
address address data code language
======== ======== ======== ========= =============
// H emulates the first seven instructions of P ...[00001352][0021233e][00212342] 55 push ebp // enter P
...[00001353][0021233e][00212342] 8bec mov ebp,esp ...[00001355][0021233e][00212342] 8b4508 mov eax,[ebp+08] ...[00001358][0021233a][00001352] 50 push eax // push P
...[00001359][0021233a][00001352] 8b4d08 mov ecx,[ebp+08] ...[0000135c][00212336][00001352] 51 push ecx // push P
...[0000135d][00212332][00001362] e840feffff call 000011a2 // call H
// The emulated H emulates the first seven instructions of P ...[00001352][0025cd66][0025cd6a] 55 push ebp // enter P
...[00001353][0025cd66][0025cd6a] 8bec mov ebp,esp ...[00001355][0025cd66][0025cd6a] 8b4508 mov eax,[ebp+08] ...[00001358][0025cd62][00001352] 50 push eax // push P
...[00001359][0025cd62][00001352] 8b4d08 mov ecx,[ebp+08] ...[0000135c][0025cd5e][00001352] 51 push ecx // push P
...[0000135d][0025cd5a][00001362] e840feffff call 000011a2 // call H
Local Halt Decider: Infinite Recursion Detected Simulation Stopped
--- SoupGate-Win32 v1.05
* Origin: fsxNet Usenet Gateway (21:1/5)