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

#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
void P(ptr x)
{
H(x, x);
}

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

It is obvious that whether or not the above code is directly executed or
H performs a pure simulation of its input that the above code specifies infinite recursion.

If H simulates its input in debug step mode it can correctly abort the simulation of this input as soon as H sees its simulated P call itself
with the same parameters that it was called with. When it does this it correctly returns 0 for not halting.

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

No computation halts (even if it stops running) unless it reaches its
final state

Because there is nothing that any 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.

Because the simulated or executed input to every H(P,P) invoked at
machine address 00001a7e with the byte sequence of the machine code of P
as its input never reaches the final address of P at 00001a72 it is
always correct for this H(P,P) to return 0.

All rebuttals must take this form:
Find an invocation of H(P,P) at machine address 00001a7e such that the simulation or execution of (the exact byte sequence of) P reaches its
final address of 00001a72.

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)


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