On Fri, 12 Nov 2021 17:35:59 -0600, olcott <
NoOne@NoWhere.com> 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
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)
You cannot always detect cases of infinite recursion without infinite resources.
/Flibble
--- SoupGate-Win32 v1.05
* Origin: fsxNet Usenet Gateway (21:1/5)