XPost: comp.theory, sci.logic, sci.math
On 10/31/2021 6:00 AM, Richard Damon wrote:
On 10/30/21 10:44 PM, olcott wrote:
When we examine pages 4 and 5 and hypothesize
that H is merely a pure simulator we can see
that when P calls H at its machine address 0xc41
that this **is** infinitely nested simulation
such that P never reaches its final state.
The only other possibility is that H is a halt
decider that aborts its simulation of P at the
machine address 0xc41 of P. In this case P also
never reaches is final state at machine address
0xc50. Thus in every possibility P never reaches
its final state and thus never halts.
https://www.researchgate.net/publication/351947980_Halting_problem_undecidability_and_infinitely_nested_simulation
Yes, if H IS a 'pure simulator', then H^/P will be non-halting. But H
doesn't get this case right, as H never answers.
This fact ONLY applies if H is actually a Pure Simulator, and in no
other case.
// Simplified Linz Ĥ (Linz:1990:319)
// Strachey(1965) CPL translated to C
void P(u32 x)
{
if (H(x, x))
HERE: goto HERE;
}
int main()
{
Output("Input_Halts = ", H((u32)P, (u32)P));
}
_P()
[00000c36](01) 55 push ebp
[00000c37](02) 8bec mov ebp,esp
[00000c39](03) 8b4508 mov eax,[ebp+08] // 2nd Param
[00000c3c](01) 50 push eax
[00000c3d](03) 8b4d08 mov ecx,[ebp+08] // 1st Param
[00000c40](01) 51 push ecx
[00000c41](05) e820fdffff call 00000966 // call H
[00000c46](03) 83c408 add esp,+08
[00000c49](02) 85c0 test eax,eax
[00000c4b](02) 7402 jz 00000c4f
[00000c4d](02) ebfe jmp 00000c4d
[00000c4f](01) 5d pop ebp
[00000c50](01) c3 ret
Size in bytes:(0027) [00000c50]
_main()
[00000c56](01) 55 push ebp
[00000c57](02) 8bec mov ebp,esp
[00000c59](05) 68360c0000 push 00000c36 // push P
[00000c5e](05) 68360c0000 push 00000c36 // push P
[00000c63](05) e8fefcffff call 00000966 // call H(P,P)
[00000c68](03) 83c408 add esp,+08
[00000c6b](01) 50 push eax
[00000c6c](05) 6857030000 push 00000357
[00000c71](05) e810f7ffff call 00000386
[00000c76](03) 83c408 add esp,+08
[00000c79](02) 33c0 xor eax,eax
[00000c7b](01) 5d pop ebp
[00000c7c](01) c3 ret
Size in bytes:(0039) [00000c7c]
machine stack stack machine assembly
address address data code language
======== ======== ======== ========= ============= [00000c56][0010172a][00000000] 55 push ebp [00000c57][0010172a][00000000] 8bec mov ebp,esp [00000c59][00101726][00000c36] 68360c0000 push 00000c36 // push P [00000c5e][00101722][00000c36] 68360c0000 push 00000c36 // push P [00000c63][0010171e][00000c68] e8fefcffff call 00000966 // call H(P,P)
Begin Local Halt Decider Simulation at Machine Address:c36 [00000c36][002117ca][002117ce] 55 push ebp [00000c37][002117ca][002117ce] 8bec mov ebp,esp [00000c39][002117ca][002117ce] 8b4508 mov eax,[ebp+08] [00000c3c][002117c6][00000c36] 50 push eax // push P [00000c3d][002117c6][00000c36] 8b4d08 mov ecx,[ebp+08] [00000c40][002117c2][00000c36] 51 push ecx // push P [00000c41][002117be][00000c46] e820fdffff call 00000966 // call H(P,P)
[00000c36][0025c1f2][0025c1f6] 55 push ebp [00000c37][0025c1f2][0025c1f6] 8bec mov ebp,esp [00000c39][0025c1f2][0025c1f6] 8b4508 mov eax,[ebp+08] [00000c3c][0025c1ee][00000c36] 50 push eax // push P [00000c3d][0025c1ee][00000c36] 8b4d08 mov ecx,[ebp+08] [00000c40][0025c1ea][00000c36] 51 push ecx // push P [00000c41][0025c1e6][00000c46] e820fdffff call 00000966 // call H(P,P)
Local Halt Decider: Infinite Recursion Detected Simulation Stopped
The input to H(P,P) never reaches its final state at its machine address
0xc50 whether or not H(P,P) aborts the simulation of this input
therefore we can definitely conclude that the input to H(P,P) never halts.
In your second case, yes, the partial simulation by H of P does not
reach a halting state, but that does NOT show that P is non-halting, to
claim it does is a logical failicy.
If we examine every possible case and find that the input to H(P,P)
never reaches its final state in any of them then it is necessarily true
that the input to H(P,P) never halts.
We do see that if H aborts its simulation of a copy of P and returns non-halting, then another copy of P that uses a copy of this H will get
that non-halting answer and then Halt,
Not in the above case.
[00000c68][0010172a][00000000] 83c408 add esp,+08 [00000c6b][00101726][00000000] 50 push eax [00000c6c][00101722][00000357] 6857030000 push 00000357 [00000c71][00101722][00000357] e810f7ffff call 00000386
Input_Halts = 0
[00000c76][0010172a][00000000] 83c408 add esp,+08 [00000c79][0010172a][00000000] 33c0 xor eax,eax [00000c7b][0010172e][00100000] 5d pop ebp [00000c7c][00101732][00000068] c3 ret
Number_of_User_Instructions(27)
H(P,P) is simulating its input. P invokes another instance of H to
simulate itself. When this second P is about to invoke another instance
of H, the outermost H aborts its outermost P thus terminating the entire simulation hierarchy.
So the question comes down to this:
(a) If H(P,P) never aborts the simulation of its input then its input
never reaches its final state.
(b) If H(P,P) aborts the simulation of its input then its input never
reaches its final state.
If H aborts the simulation of its input then the whole simulation
hierarchy has been aborted because the whole simulation hierarchy
depends on the execution of the outermost P.
showing us that P(P) is actually
a Halting Computation.
You mistaken claim that a partial simulation shows non-halting or that
you can use different Hs when running P by itself vs what the halt
decider is.
I have shown that the input to H(P,P) never reaches its final state in
every possible case therefore it is necessarily correct that the input
to H(P,P) never halts.
Note, your claim that you can replace the simulation of a machine with
the direct execution of that machine ONLY applies if the simulation is
truely 'pure' or never aborted, so using that model implies that H can
only be that real pure simulator that we have shown never answers H(P,P)
and thus fails to meet the basic requirements of a halt decider.
The transform does NOT apply to a 'pure simulator until...' machine.
--
Copyright 2021 Pete Olcott
"Great spirits have always encountered violent opposition from mediocre
minds." Einstein
--- SoupGate-Win32 v1.05
* Origin: fsxNet Usenet Gateway (21:1/5)