After very extensive discussions (23 emails) with a leading computer
scientist I have a much simpler way to make my point.

typedef void (*ptr)();

void P(ptr x)
{ if (H(x, x))
HERE: goto HERE;
return;
}

int main()
{ Output("Input_Halts = ", H(P, P));
}

*H and P implement this pathological relationship*
For any program H that might determine if programs halt, a
"pathological" program P, called with some input, can pass its own
source and its input to H and then specifically do the opposite of what
H predicts P will do. No H can exist that handles this case.
https://en.wikipedia.org/wiki/Halting_problem

All of the conventional proofs of the halting problem (including the
diagonalization proof) correctly prove that H cannot possibly return a
correct halt status to its caller P.

None of these proofs ever notice that when H is a simulating halt
decider it cannot possibly correctly return any value to the simulated P
because no function that is (essentially) called in infinite recursion
ever returns to its caller.

This provides the basis for H(P,P) to correctly determine that its
correct and complete simulation of its input would never reach the final
state of this simulated input, thus never halts.

*Once this halt deciding principle is accepted*
A halt decider must compute the mapping from its inputs to an accept or
reject state on the basis of the actual behavior that is actually
specified by these inputs.

*Then this method is understood to implement that principle*
Every simulating halt decider that correctly simulates its input until
it correctly predicts that this simulated input would never reach its
final state, correctly rejects this input as non-halting.

--
Copyright 2022 Pete Olcott

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

On 7/10/22 9:54 PM, olcott wrote:
> After very extensive discussions (23 emails) with a leading computer
> scientist I have a much simpler way to make my point.
>
> typedef void (*ptr)();
>
> void P(ptr x)
> {
>   if (H(x, x))
>     HERE: goto HERE;
>   return;
> }
>
> int main()
> {
>   Output("Input_Halts = ", H(P, P));
> }
>
> *H and P implement this pathological relationship*
> For any program H that might determine if programs halt, a
> "pathological" program P, called with some input, can pass its own
> source and its input to H and then specifically do the opposite of what
> H predicts P will do. No H can exist that handles this case.
> https://en.wikipedia.org/wiki/Halting_problem
>
> All of the conventional proofs of the halting problem (including the
> diagonalization proof) correctly prove that H cannot possibly return a
> correct halt status to its caller P.
>
> None of these proofs ever notice that when H is a simulating halt
> decider it cannot possibly correctly return any value to the simulated P
> because no function that is (essentially) called in infinite recursion
> ever returns to its caller.

So, an H that does that can't be a proper Halt Decider.

You can't make H be BOTH a simulating Halt Decider that simulates
forever, and also one that aborts its simulation to answer. (Not until
you find a way to do infinite work in a finite number of steps).

>
> This provides the basis for H(P,P) to correctly determine that its
> correct and complete simulation of its input would never reach the final
> state of this simulated input, thus never halts.
>

But if H does that, then you just said it can't return the answer, so if
it return an answer, it didn't do that, so you can't assume it does.

> *Once this halt deciding principle is accepted*
> A halt decider must compute the mapping from its inputs to an accept or
> reject state on the basis of the actual behavior that is actually
> specified by these inputs.

Right, the ACTUAL behavior, and if P and H are the required functions,
H(P,P) must return the correct behavior of P(P), and since P(P) will
Halt if H(P,P) returns 0, H(P,P) returning 0 can not be a correct answer.

>
> *Then this method is understood to implement that principle*
> Every simulating halt decider that correctly simulates its input until
> it correctly predicts that this simulated input would never reach its
> final state, correctly rejects this input as non-halting.
>

Right, and you need to prove that it WILL correctly predict that this
simulated input would never reach its final state, and do so in a finite
number of steps.

Since, for ANY finite pattern that exists in the simulation of the input
to H(P,P), if H detects that as a "proven non-halting pattern", and
aborts its simulation, and returns 0, since P is DEFINED to use THAT H,
when P(P) calls H(P,P) it WILL return the value 0 in finite time, and
thus halt, we see that there does not exist a pattern that H can use to
correctly decide.

Thus, your Halt Decider H MUST, to avoid making an error, continue to
simulate its input forever, and thus fail to answer.

Please post this to comp.theory _only_ !

Am 11.07.2022 um 03:54 schrieb olcott:
> After very extensive discussions (23 emails) with a leading computer
> scientist I have a much simpler way to make my point.
>
> typedef void (*ptr)();
>
> void P(ptr x)
> {
>   if (H(x, x))
>     HERE: goto HERE;
>   return;
> }
>
> int main()
> {
>   Output("Input_Halts = ", H(P, P));
> }
>
> *H and P implement this pathological relationship*
> For any program H that might determine if programs halt, a
> "pathological" program P, called with some input, can pass its own
> source and its input to H and then specifically do the opposite of what
> H predicts P will do. No H can exist that handles this case.
> https://en.wikipedia.org/wiki/Halting_problem
>
> All of the conventional proofs of the halting problem (including the
> diagonalization proof) correctly prove that H cannot possibly return a
> correct halt status to its caller P.
>
> None of these proofs ever notice that when H is a simulating halt
> decider it cannot possibly correctly return any value to the simulated P
> because no function that is (essentially) called in infinite recursion
> ever returns to its caller.
>
> This provides the basis for H(P,P) to correctly determine that its
> correct and complete simulation of its input would never reach the final
> state of this simulated input, thus never halts.
>
> *Once this halt deciding principle is accepted*
> A halt decider must compute the mapping from its inputs to an accept or
> reject state on the basis of the actual behavior that is actually
> specified by these inputs.
>
> *Then this method is understood to implement that principle*
> Every simulating halt decider that correctly simulates its input until
> it correctly predicts that this simulated input would never reach its
> final state, correctly rejects this input as non-halting.
>