Peter Olcott admitted his H is NOT an halt decider

35 views
Skip to first unread message

Python

unread,
Aug 12, 2022, 1:41:29 PMAug 12
to
In message: <k9adnWtx-dZH62v_...@giganews.com>, on 12 of
August 2022,

Peter Olcott has admitted that his H does not satisfy:

H(X,Y)==0 if and only if X(Y) does not halt

so his H is NOT AN HALT DECIDER. PERIOD.


olcott

unread,
Aug 12, 2022, 2:28:30 PMAug 12
to
A simulating halt decider simulates its input until it correctly proves
that this simulation would never stop unless aborted.

typedef void (*ptr)();
int H(ptr p, ptr i); // simulating halt decider

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

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

(1) I believe that most computer scientists would agree that a halt
decider must compute the mapping from its inputs to an accept or reject
state on the basis of the actual behavior specified by this input.

(2) Furthermore ALL computer scientists would agree that the correct
simulation of a machine description does derive the correct behavior
specified by this machine description.

This logically entails that when H(P,P) simulates its input until the
behavior of this input essentially matches the infinite recursion
behavior pattern, then H has correctly determined the halt status of P.

(a) The invoked H(P,P) simulates P(P) that calls a simulated H(P,P)
(b) that simulates P(P) that calls a simulated H(P,P)
(c) that simulates P(P) that calls a simulated H(P,P)...
Until H aborts the simulation of its input

I have "admitted" that (1) & (2) logically entails that H(P,P)==0 is
correct and if (1) & (2) is true then this proves that the assertion
that H(P,P) must be based on the behavior of P(P) is incorrect.

In other words the textbook definition of the halting function is proven
to be incorrect on the basis that it contradicts (1) & (2).

*Halting problem proofs refuted on the basis of software engineering* ?
https://www.researchgate.net/publication/361701808_Halting_problem_proofs_refuted_on_the_basis_of_software_engineering


--
Copyright 2022 Pete Olcott

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

Ben Bacarisse

unread,
Aug 12, 2022, 3:47:06 PMAug 12
to
This was made clear a few years ago. He covers it up from time to time,
so it's good it's back out in the open, but it's not really news.

In fact almost everything he has done since the manic post in Dec 2018
when he claimed to have "two actual Turing machines", H and H^, "exactly
and precisely as in Linz" "fully encoded" has been to find a way to
un-say this without it sounding too obviously wrong.

For a while, there was a patch of comparatively clear post-hoc
justification going on: H(P,P) == 0 is correct even though P(P) halts
because ... (insert your favourite of several reason here)[1] but that
was way too clear.

[1] Mine is "because P(P) would not halt if line 15 of H were commented
out"!

--
Ben.

Paul N

unread,
Aug 12, 2022, 3:48:08 PMAug 12
to
It's not so much that the definition is "incorrect" - how can a definition be incorrect? - but that no H can be found that will meet it. That is what other people have proved, and you have not refuted those proofs.

olcott

unread,
Aug 12, 2022, 4:00:07 PMAug 12
to
A simulating halt decider simulates its input until it correctly proves
that this simulation would never stop unless aborted.

typedef void (*ptr)();
int H(ptr p, ptr i); // simulating halt decider

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

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

The only way to show that the halting function is defined correctly is
to find an error in (1) or (2).

(1) I believe that most computer scientists would agree that a halt
decider must compute the mapping from its inputs to an accept or reject
state on the basis of the actual behavior specified by this input.

(2) Furthermore ALL computer scientists would agree that the correct
simulation of a machine description does derive the correct behavior
specified by this machine description.

This logically entails that when H(P,P) simulates its input until the
behavior of this input essentially matches the infinite recursion
behavior pattern, then H has correctly determined the halt status of P.

If (1) & (2) are true then this proves that the definition of the
halting function requiring H(P,P) to base its halt status decision on
the behavior of non-input P(P) is incorrect.

*Finding an error in (1) or (2) is the only way to*
*show that the halting function is defined correctly*

*Finding an error in (1) or (2) is the only way to*
*show that the halting function is defined correctly*

*Finding an error in (1) or (2) is the only way to*
*show that the halting function is defined correctly*

olcott

unread,
Aug 12, 2022, 4:01:43 PMAug 12
to
When a one definition directly contradicts another definition at most
one of them can be correct.

*Finding an error in (1) or (2) is the only way to*
*show that the halting function is defined correctly*

*Finding an error in (1) or (2) is the only way to*
*show that the halting function is defined correctly*

*Finding an error in (1) or (2) is the only way to*
*show that the halting function is defined correctly*



dklei...@gmail.com

unread,
Aug 12, 2022, 4:11:06 PMAug 12
to
On Friday, August 12, 2022 at 11:28:30 AM UTC-7, olcott wrote:
>
> (1) I believe that most computer scientists would agree that a halt
> decider must compute the mapping from its inputs to an accept or reject
> state on the basis of the actual behavior specified by this input.
>
This is the definition of halt decider.
>
> (2) Furthermore ALL computer scientists would agree that the correct
> simulation of a machine description does derive the correct behavior
> specified by this machine description.
>
This is the definition of simulation
>
> This logically entails that when H(P,P) simulates its input until the
> behavior of this input essentially matches the infinite recursion
> behavior pattern, then H has correctly determined the halt status of P.
>
This does not follow. Not all non-halting simulations ever show that
pattern.

olcott

unread,
Aug 12, 2022, 4:19:36 PMAug 12
to
On 8/12/2022 3:09 PM, dklei...@gmail.com wrote:
> On Friday, August 12, 2022 at 11:28:30 AM UTC-7, olcott wrote:
>>
>> (1) I believe that most computer scientists would agree that a halt
>> decider must compute the mapping from its inputs to an accept or reject
>> state on the basis of the actual behavior specified by this input.
>>
> This is the definition of halt decider.

Yes it is. In order to begin to show otherwise requires more than a
dogmatic statement that you believe it is incorrect, it requires
pointing out the exact error and all of the reasoning why it is an error.

>>
>> (2) Furthermore ALL computer scientists would agree that the correct
>> simulation of a machine description does derive the correct behavior
>> specified by this machine description.
>>
> This is the definition of simulation
>>
>> This logically entails that when H(P,P) simulates its input until the
>> behavior of this input essentially matches the infinite recursion
>> behavior pattern, then H has correctly determined the halt status of P.
>>
> This does not follow. Not all non-halting simulations ever show that
> pattern.
>

So you did not bother to notice that I am talking about a specific H/P ?

Dennis Bush

unread,
Aug 12, 2022, 4:26:16 PMAug 12
to
FALSE. They would agree that a halt decider must compute the halting function:

For *any* algorithm X and input Y:
H(X,Y)==1 if and only if X(Y) halts, and
H(X,Y)==0 if and only if X(Y) does not halt

And it directly follows from this that "the actual behavior specified by this input" is defined to be the behavior of X(Y), not the behavior of some simulator.

In the case of Ha(Pa,Pa), this means "the actual behavior specified by this input" is the behavior of Pa(Pa), not the behavior of Pn(Pn) as you like to claim:

On Saturday, July 30, 2022 at 4:09:34 PM UTC-4, olcott wrote:
> H(P,P) is asking would the input that I correctly emulate ever reach its
> "ret" instruction (final state) if I never stopped emulating it?

On Wednesday, August 10, 2022 at 6:11:10 PM UTC-4, olcott wrote:
> This is the correct point in the execution trace to put the simulator:
>
> void P(ptr x)
> {
> int Halt_Status = Simulate(x, x);
> if (Halt_Status)
> HERE: goto HERE;
> return;
> }


>
> (2) Furthermore ALL computer scientists would agree that the correct
> simulation of a machine description does derive the correct behavior
> specified by this machine description.

FALSE. It would be the correct AND COMPLETE simulation, not some simulation that was aborted. Counterexample: Ha3(N,5) does a correct but not complete simulation, and it is obvious that Ha3(N,5)==0 is wrong because N(5) aborts.

>
> This logically entails that when H(P,P) simulates its input until the
> behavior of this input essentially matches the infinite recursion
> behavior pattern, then H has correctly determined the halt status of P.

But what you think is an infinite behavior pattern is not as demonstrated by Pa(Pa) halting.

Richard Damon

unread,
Aug 12, 2022, 5:55:13 PMAug 12
to
On 8/12/22 2:28 PM, olcott wrote:
> On 8/12/2022 12:41 PM, Python wrote:
>> In message: <k9adnWtx-dZH62v_...@giganews.com>, on 12 of
>> August 2022,
>>
>> Peter Olcott has admitted that his H does not satisfy:
>>
>>   H(X,Y)==0 if and only if X(Y) does not halt
>>
>> so his H is NOT AN HALT DECIDER. PERIOD.
>>
>>
>
> A simulating halt decider simulates its input until it correctly proves
> that this simulation would never stop unless aborted.
>

So why does yours stop before it does that?

Because it uses UNSOUND logic and thus is wrong.

> typedef void (*ptr)();
> int H(ptr p, ptr i); // simulating halt decider
>
> void P(ptr x)
> {
>   int Halt_Status = H(x, x);
>   if (Halt_Status)
>     HERE: goto HERE;
>   return;
> }
>
> int main()
> {
>   Output("Input_Halts = ", H(P, P));
> }
>
> (1) I believe that most computer scientists would agree that a halt
> decider must compute the mapping from its inputs to an accept or reject
> state on the basis of the actual behavior specified by this input.
>
> (2) Furthermore ALL computer scientists would agree that the correct
> simulation of a machine description does derive the correct behavior
> specified by this machine description.
>
> This logically entails that when H(P,P) simulates its input until the
> behavior of this input essentially matches the infinite recursion
> behavior pattern, then H has correctly determined the halt status of P.
>
> (a) The invoked H(P,P) simulates P(P) that calls a simulated H(P,P)
> (b) that simulates P(P) that calls a simulated H(P,P)
> (c) that simulates P(P) that calls a simulated H(P,P)...
> Until H aborts the simulation of its input

Whicb isn't what happens with your H.

>
> I have "admitted" that (1) & (2) logically entails that H(P,P)==0 is
> correct and if (1) & (2) is true then this proves that the assertion
> that H(P,P) must be based on the behavior of P(P) is incorrect.

And thus you are wrong, because you don't look at a CORRECT simulation
of the input.

>
> In other words the textbook definition of the halting function is proven
> to be incorrect on the basis that it contradicts (1) & (2).

Nope, the problem is you don't have a CORRECT simulation to work from,
but incorrect presume the behavior of H, so you get the wrong answer.

dklei...@gmail.com

unread,
Aug 13, 2022, 12:28:43 AMAug 13
to
On Friday, August 12, 2022 at 1:19:36 PM UTC-7, olcott wrote:
> On 8/12/2022 3:09 PM, dklei...@gmail.com wrote:
> > On Friday, August 12, 2022 at 11:28:30 AM UTC-7, olcott wrote:
> >>
> >> (1) I believe that most computer scientists would agree that a halt
> >> decider must compute the mapping from its inputs to an accept or reject
> >> state on the basis of the actual behavior specified by this input.
> >>
> > This is the definition of halt decider.
> Yes it is. In order to begin to show otherwise requires more than a
> dogmatic statement that you believe it is incorrect, it requires
> pointing out the exact error and all of the reasoning why it is an error.
> >>
> >> (2) Furthermore ALL computer scientists would agree that the correct
> >> simulation of a machine description does derive the correct behavior
> >> specified by this machine description.
> >>
> > This is the definition of simulation
> >>
> >> This logically entails that when H(P,P) simulates its input until the
> >> behavior of this input essentially matches the infinite recursion
> >> behavior pattern, then H has correctly determined the halt status of P.
> >>
> > This does not follow. Not all non-halting simulations ever show that
> > pattern.
> >
> So you did not bother to notice that I am talking about a specific H/P ?

You did not say that was the case.

What specific H and P do your comments assume and how do they relate
to (1) and (2) above?
Reply all
Reply to author
Forward
0 new messages