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

Glossary of Terms

computation that halts
a computation is said to halt whenever it enters a final state.
(Linz:1990:234)

computer science decider
a decider is a machine that accepts or rejects inputs. https://cs.stackexchange.com/questions/84433/what-is-decider

halt decider
A halt decider accepts or rejects inputs on the basis of the actual
behavior specified by these inputs. Whenever the direct execution or
pure simulation of an input would never reach its final state this input
is correctly decided as not halting.

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

int H(ptr x, ptr y)
{
x(y); // direct execution of P(P)
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.

Proof that H(P,P)==0 for every possible H at machine address 00001a7e
that simulates or executes the precise byte sequence shown below:

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

P is defined as the above precise byte sequence.
The x86 language is the entire inferece basis.

For every possible H defined at machine address 00001a7e that has input
(P,P)
when the input to H(P,P) is executed or simulated this input is either infinitely recursive or aborted at some point. In no case does the input
ever reach its final state of 00001a72.

For every possible H at machine address 00001a7e that executes or
simulates its input the input to H(P,P) never halts. For all specified
H/P combinations H(P,P)==0 is always correct.



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



--
Copyright 2021 Pete Olcott

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

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