Giving credit where credit is due
Ben posted these very excellent improvements
to my initial syntax in comp.lang.c
On 11/11/2021 2:31 PM, Ben Bacarisse wrote:

#include <stdint.h>
typedef void (*ptr)();

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

// Minimal essence of Linz(1990) Ĥ
// and Strachey(1965) P (see below)
void P(ptr x)
{ H(x, x);
}

int main(void)
{ H(P, P);
}

It is obvious that the direct execution of the above code never halts
because it is infinitely recursive. It is equally obvious that when H
performs a correct pure simulation of its input (instead of directly
executing it) that its input never halts.

_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]

Because there is nothing that H can possibly do to cause or enable P to
reach its final state at 1a72 we correctly conclude that the input to
H(P,P) never halts.

// Simplified Linz(1990) Ĥ and Strachey(1965) P
void P(u32 x)
{ if (H(x, x))
HERE: goto HERE;
}

Halting problem undecidability and infinitely nested simulation (V2)
November 2021 PL Olcott

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

Strachey, C 1965. An impossible program The Computer Journal, Volume 7,
Issue 4, January 1965, Page 313, https://doi.org/10.1093/comjnl/7.4.313

Linz, Peter 1990. An Introduction to Formal Languages and Automata.
Lexington/Toronto: D. C. Heath and Company. (318-320)

Talent hits a target no one else can hit;
Genius hits a target no one else can see. Arthur Schopenhauer

--
Copyright 2021 Pete Olcott

"Great spirits have always encountered violent opposition from mediocre
minds." Einstein

On 11/12/21 1:48 PM, olcott wrote:
> Giving credit where credit is due
> Ben posted these very excellent improvements
> to my initial syntax in comp.lang.c
> On 11/11/2021 2:31 PM, Ben Bacarisse wrote:
>
> #include <stdint.h>
> typedef void (*ptr)();
>
> int H(ptr x, ptr y)
> {
>   x(y);
>   return 1;
> }
>
> // Minimal essence of Linz(1990) Ĥ
> // and Strachey(1965) P (see below)
> void P(ptr x)
> {
>   H(x, x);
> }
>
> int main(void)
> {
>   H(P, P);
> }
>
> It is obvious that the direct execution of the above code never halts
> because it is infinitely recursive. It is equally obvious that when H
> performs a correct pure simulation of its input (instead of directly
> executing it) that its input never halts.
>
> _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]
>
> Because there is nothing that H can possibly do to cause or enable P to
> reach its final state at 1a72 we correctly conclude that the input to
> H(P,P) never halts.
>
>

Yes, for THAT H, the H^/P built on it is non-halting, but THAT H fails
to say that, as it never returns an answer.

Thus, this H is not a counter example for the Halting Problem.

Since the behavior of H^/P is dependent on the behavior of H, if you
change H to try to give that answer, you can't use this case for any
evidence about the behavior of the P built by the new H.

That would be like running tests on your neighbors cat to determine
something about your dog.

>

>
>
>
>
>
>
>
> // Simplified Linz(1990) Ĥ and Strachey(1965) P
> void P(u32 x)
> {
>   if (H(x, x))
>     HERE: goto HERE;
> }
>
> Halting problem undecidability and infinitely nested simulation (V2)
> November 2021 PL Olcott
>
> https://www.researchgate.net/publication/356105750_Halting_problem_undecidability_and_infinitely_nested_simulation_V2
>
>
> Strachey, C 1965.  An impossible program The Computer Journal, Volume 7,
> Issue 4, January 1965, Page 313, https://doi.org/10.1093/comjnl/7.4.313
>
> Linz, Peter 1990. An Introduction to Formal Languages and Automata.
> Lexington/Toronto: D. C. Heath and Company. (318-320)
>
> Talent hits a target no one else can hit;
> Genius hits a target no one else can see. Arthur Schopenhauer
>
>
>