XPost: comp.theory, sci.logic, sci.math

Does the call from P() to H() specify infinite recursion?

#include <stdint.h>
#define ptr uintptr_t

void P(ptr x)
{
H(x, x);
}

int H(ptr x, ptr y)
{
((void(*)(ptr))x)(y);
return 1;
}

int main()
{
H((ptr)P, (ptr)P);
return 0;
}

Yes it does.

_P()
[00001a5e](01) 55 push ebp
[00001a5f](02) 8bec mov ebp,esp
[00001a61](03) 8b4508 mov eax,[ebp+08]
[00001a64](01) 50 push eax // push P
[00001a65](03) 8b4d08 mov ecx,[ebp+08]
[00001a68](01) 51 push ecx // push P
[00001a69](05) e810000000 call 00001a7e // call H
[00001a6e](03) 83c408 add esp,+08
[00001a71](01) 5d pop ebp
[00001a72](01) c3 ret
Size in bytes:(0021) [00001a72]

Now we switch H executing its input to H simulating its input. H
simulates the x86 machine language of its input and sees that its
simulated P is calling H with the same parameters that H was called
with. On this basis H aborts its simulation of P and correctly reports
that P would never reach its final state at 1a72. Because H and P are
both pure functions we know that H(P,P)==0 is computable.

(a) P only halts if it reaches its final state at 1a72.
(b) If H does not abort its simulation of P then P never reaches its
final state at 1a72.
(c) If H aborts its simulation of P then P never reaches its final state
as 1a72.
(d) Because P never halts in all possible cases H(P,P)==0 is always
correct.

The fact that there are no errors in (a)(b)(c) and (d) is a necessary consequence of (a)(b)(c) conclusively proves that (d) is correct.


Halting problem undecidability and infinitely nested simulation (V2)

https://www.researchgate.net/publication/356105750_Halting_problem_undecidability_and_infinitely_nested_simulation_V2


--
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)