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

Concise refutation of halting problem proofs V37 [ Olcott 2021 generic halt deciding principle ]

1 view
Skip to first unread message

olcott

unread,
Dec 4, 2021, 4:24:32 PM12/4/21
to
[Olcott 2021 generic halt deciding principle]
Whenever the pure simulation of the input to simulating halt decider
H(x,y) never stops running unless H aborts its simulation H correctly
aborts this simulation and returns 0 for not halting.

Halting problem
In computability theory, the halting problem is the problem of
determining, from a description of an arbitrary computer program and an
input, whether the program will finish running, or continue to run
forever. https://en.wikipedia.org/wiki/Halting_problem

Now we construct a new Turing machine D with H as a subroutine.
This new TM calls H to determine what M does when the input to M
is its own description ⟨M⟩. Once D has determined this information,
it does the opposite. (Sipser:1997:165)

// Simplified Linz(1990) Ĥ
// and Strachey(1965) P
void P(ptr x)
{
if (H(x, x))
HERE: goto HERE;
}

The pathological feedback loop between the halt decider and its input
that otherwise makes inputs like the above impossible for H(P,P) to
decide has been eliminated.

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