Google Groups no longer supports new Usenet posts or subscriptions. Historical content remains viewable.
Dismiss

Concise refutation of halting problem proofs V33

2 views
Skip to first unread message

olcott

unread,
Nov 27, 2021, 9:45:02 AM11/27/21
to
#include <stdint.h>
#include <stdio.h>
typedef int (*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
int P(ptr x)
{
H(x, x);
return 1; // Give P a last instruction at the "c" level
}

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

The above program is obviously infinitely recursive. It is self evident
that when 0 to ∞ steps of the input to H(P,P) are directly executed or
correctly simulated that the input to H(P,P) never reaches its final
instruction.

computation that halts a computation halts whenever it enters a final
state (Linz:1990:234) thus none of the simulated or executed 0 to ∞
steps of the input to H(P,P) ever halt.

PSR set (pathological self-reference)
H1(P1,P1) Is the above code.
H2(P2,P2) Is the above code where H2 simulates rather than directly
executes its input.
H3(P3,P3) Is the execution of N steps of the input of H1(P1,P1).
H4(P4,P4) Is the simulation of N steps of the input of H2(P2,P2).

Every Hn(Px,Py) that returns a value returns 1 except for instances of
{H3, H4} that determine whether or not to return {0,1} on the basis of
the behavior of their input.

The correct pure simulation of N steps of the input to H(P,P) by H is
always a correct halt deciding basis where P has reached its final state
or H has correctly detected that P would never reach its final state.

The point in the sequence of N steps where the execution trace of the
simulation of P shows that P is about to call H(P,P) again with the same
input that H was called with provides conclusive proof that P would be
infinitely recursive unless H aborted its simulation.
*In this H4(P4,P4)==0 computation P4 is dependent on H4 altering the
behavior of P4.*

When directly executed P(P) calls H(P,P) and the simulated P(P) reaches
the point where it would call H(P,P) with the same parameters that H was
called with H returns 0 to this directly executed P.
*In this H1(P4,P4)==1 computation P4 is independent of H1.*

H is a computable function that accepts or rejects inputs in its domain
on the basis that these inputs specify a sequence of configurations that
reach their final state.




Halting problem undecidability and infinitely nested simulation (V2)

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
0 new messages