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

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

--- SoupGate-Win32 v1.05
* Origin: fsxNet Usenet Gateway (21:1/5)