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

On 11/11/21 2:35 PM, olcott wrote:
> 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.

Except that this 'transform' has only been shown to be correct if the
simulator is unconditional.

You are making the logical falicy of assuming the general case from a
proof of the specific.

It can be CLEARLY seen that if the outer H doing this simulation might
decide to abort its simulation, then when it simulates an exact copy of
itself (or even itself) that this copy will do the same thing, and thus
the execution will NOT be infinite.

FAIL.

>
> (a) P only halts if it reaches its final state at 1a72.

Right, in an ACTUAL running of P or a UNCONDITIONAL simulation of P.

A partial simulation that doesn't reach that instruction doesn't
actually prove anything.

> (b) If H does not abort its simulation of P then P never reaches its
> final state at 1a72.

Right, Hb that never aborts its simulation creates a Pb that will never
halt when computing Pb(Pb), but your problem is that it is also a fact
that Hb(Pb,Pb) never gets around to returning the 0 to say that this
happens, so Hb is not a valid counter example.

> (c) If H aborts its simulation of P then P never reaches its final state
> as 1a72.

WRONG. It may be true that the ABORTED simulation in Hc didn't reach
that final state, but as mentioned above, that doesn't matter. What does
matter is that Pc, built on this Hc when computing Pc(Pc) does Halt, you
have admited to this yourself.

> (d) Because P never halts in all possible cases H(P,P)==0 is always
> correct.

FALSE. Yes H(Pb,Pb) == 0 is true, but Hb(Pb,Pb) never returns that
answer. Yes Hc(Pb,Pb) return 0, but that is irrelevent.

As shown above the CORRECT answer for H(Pc,Pc) is 1, and it is infact a
case the Hb(Pc,Pc) will return that answer which helps to confirm it
(but doesn't help your claim). The fact that Hc(P,Pc) INCORRECTLY
returns 0 shows that Hc is wrong.

Your 'Proof' conflates the b and c versions of the functions, and gets
the wrong anser.

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

But there are many error in (a) (b) (c) and (d).

>
> Halting problem undecidability and infinitely nested simulation (V2)
>
> https://www.researchgate.net/publication/356105750_Halting_problem_undecidability_and_infinitely_nested_simulation_V2
>
>