XPost: comp.theory, sci.logic

On 10/17/2022 11:45 AM, Mr Flibble wrote:

On Mon, 17 Oct 2022 11:42:22 -0500
olcott <polcott2@gmail.com> wrote:

On 10/17/2022 11:33 AM, Dennis Bush wrote:

On Monday, October 17, 2022 at 12:29:34 PM UTC-4, olcott wrote:

On 10/17/2022 11:25 AM, Dennis Bush wrote:

On Monday, October 17, 2022 at 12:15:27 PM UTC-4, olcott wrote:

On 10/17/2022 11:00 AM, Dennis Bush wrote:

On Monday, October 17, 2022 at 11:57:18 AM UTC-4, olcott wrote:

On 10/17/2022 10:47 AM, Dennis Bush wrote:

On Monday, October 17, 2022 at 11:44:10 AM UTC-4, olcott
wrote:

On 10/17/2022 10:40 AM, Dennis Bush wrote:

On Monday, October 17, 2022 at 11:31:41 AM UTC-4, olcott >>>>>>>>>>> wrote:

On 10/17/2022 10:16 AM, Dennis Bush wrote:

On Monday, October 17, 2022 at 11:06:45 AM UTC-4, olcott >>>>>>>>>>>>> wrote:

On 10/17/2022 9:49 AM, Dennis Bush wrote:

On Monday, October 17, 2022 at 10:38:09 AM UTC-4, >>>>>>>>>>>>>>> olcott wrote:

On 10/17/2022 7:47 AM, Dennis Bush wrote:

On Monday, October 17, 2022 at 5:30:59 AM UTC-4, >>>>>>>>>>>>>>>>> Fred. Zwarts wrote:

I have been following the discussions about Halt >>>>>>>>>>>>>>>>>> deciders with interest. As a retired software >>>>>>>>>>>>>>>>>> designer and developer, I have a lot of practical >>>>>>>>>>>>>>>>>> experience, but not much theoretical education, >>>>>>>>>>>>>>>>>> although the theoretical background is very >>>>>>>>>>>>>>>>>> interesting. I learned a lot. I would like to verify >>>>>>>>>>>>>>>>>> that I understand it correctly. Could you point out >>>>>>>>>>>>>>>>>> any errors in the summary below?

1) (Definition of halt) A program X with input Y is >>>>>>>>>>>>>>>>>> said to halt if it reaches its end condition after a >>>>>>>>>>>>>>>>>> finite number of steps. It does not halt if it >>>>>>>>>>>>>>>>>> continues to execute infinitely. (So, X(Y) either >>>>>>>>>>>>>>>>>> halts, or it does not halt.) (It is irrelevant >>>>>>>>>>>>>>>>>> whether the end condition is reached in the 'normal' >>>>>>>>>>>>>>>>>> way, or by other means, e.g. an unhandled
'exception'.)

2) (Definition of halt decider) A halt decider H is >>>>>>>>>>>>>>>>>> a program that, given a program X with input Y >>>>>>>>>>>>>>>>>> decides, after a finite number of steps, whether >>>>>>>>>>>>>>>>>> X(Y) halts or not. (H(X,Y) itself must halt after a >>>>>>>>>>>>>>>>>> finite number of steps. It must return either 1 if >>>>>>>>>>>>>>>>>> X(Y) halts, or 0 if X(Y) does not halt, where 1 and >>>>>>>>>>>>>>>>>> 0 are a convention, which could also be two other >>>>>>>>>>>>>>>>>> arbitrary values.)

From 1 and 2 it follows:

3) If X(Y) halts, then H must return 1. If H does >>>>>>>>>>>>>>>>>> not return 1 in a finite number of steps, it might >>>>>>>>>>>>>>>>>> return another interesting result, but it is not a >>>>>>>>>>>>>>>>>> halt decider. (Not returning 1 includes returning >>>>>>>>>>>>>>>>>> other values, not halting, or throwing 'exceptions'.) >>>>>>>>>>>>>>>>>>
4) If X(Y) does not halt, then H must return 0. If >>>>>>>>>>>>>>>>>> it does not return 0 in a finite number of steps, it >>>>>>>>>>>>>>>>>> might return another interesting result, but it is >>>>>>>>>>>>>>>>>> not a halt decider. (Not returning 0 includes >>>>>>>>>>>>>>>>>> returning other values, not halting, or throwing >>>>>>>>>>>>>>>>>> 'exceptions'.)

Paradoxical program:

5) It is always possible to construct a program P, >>>>>>>>>>>>>>>>>> that uses code with the same logic as H, in order to >>>>>>>>>>>>>>>>>> do the opposite of what H(P,P) returns. (P does not >>>>>>>>>>>>>>>>>> necessarily need to use the exact same code as H >>>>>>>>>>>>>>>>>> does, amongst others it could use a modified copy of >>>>>>>>>>>>>>>>>> H, or a simulation of H.)

From 5 it follows that a general halt decider that >>>>>>>>>>>>>>>>>> works for any X and Y does not exist:

From 3, 4 and 5 it follows:

6) If P(P) halts, then H should return 1, but if H >>>>>>>>>>>>>>>>>> would do so, P(P) would not halt.

7) If P(P) does not halt, H should return 0, but if >>>>>>>>>>>>>>>>>> H would do so, P(P) would halt.

8) If P(P) halts and H does not return 1 after a >>>>>>>>>>>>>>>>>> finite number of steps, then H is not a halt decider. >>>>>>>>>>>>>>>>>> (The result could nevertheless be interesting for >>>>>>>>>>>>>>>>>> other purposes.) (It is irrelevant what causes P(P) >>>>>>>>>>>>>>>>>> to halt.)

9) If P(P) does not halt and H does not return 0 >>>>>>>>>>>>>>>>>> after a finite number of steps, then H is not a halt >>>>>>>>>>>>>>>>>> decider. (The result could nevertheless be >>>>>>>>>>>>>>>>>> interesting for other purposes.)

Your understanding is correct. To sum things up, the >>>>>>>>>>>>>>>>> halting function (using the mathematical notion of a >>>>>>>>>>>>>>>>> function), performs the following mapping:

For *any* algorithm (i.e. a fixed immutable sequence >>>>>>>>>>>>>>>>> of instructions) 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 the halting problem proofs show that this mapping >>>>>>>>>>>>>>>>> is not computable, i.e. it is impossible for an >>>>>>>>>>>>>>>>> algorithm to compute this mapping.

*Professor Sipser has agreed to these verbatim words* >>>>>>>>>>>>>>>> (and no more) If simulating halt decider H correctly >>>>>>>>>>>>>>>> simulates its input D until H correctly determines >>>>>>>>>>>>>>>> that its simulated D would never stop running unless >>>>>>>>>>>>>>>> aborted then H can abort its simulation of D and >>>>>>>>>>>>>>>> correctly report that D specifies a non-halting >>>>>>>>>>>>>>>> sequence of configurations.

And he agreed to those words based on their commonly >>>>>>>>>>>>>>> known meanings, not your alternate weasel-word meanings. >>>>>>>>>>>>>>>
The conventional definition of "correctly simulating" >>>>>>>>>>>>>>> means that the simulated behavior EXACTLY matches the >>>>>>>>>>>>>>> behavior of direct execution.

I have proven an exception to this rule:

That's not a rule. It's a definition.

int Sipser_D(int (*M)())
{
if ( Sipser_H(M, M) )
return 0;
return 1;
}

For the infinite set of H/D pairs:
Every correct simulation of D by H will never reach the >>>>>>>>>>>>>> final state of D because D specifies recursive
simulation to H.

So in other words your Sipser_H is computing the
PO-halting function:

*The PO-halting function is now Sipser approved*

No it's not, because he used the actual meaning of the
words and not your weasel-worded definitions. Using the
real definitions,

*Professor Sipser has agreed to these verbatim words* (and >>>>>>>>>> no more) If simulating halt decider H correctly simulates
its input D until H correctly determines that its simulated >>>>>>>>>> D would never stop running unless aborted then H can abort >>>>>>>>>> its simulation of D and correctly report that D specifies a >>>>>>>>>> non-halting sequence of configurations. *A paraphrase of a >>>>>>>>>> portion of the above paragraph* Would D correctly simulated >>>>>>>>>> by H ever stop running if not aborted?

The answer of "no" is proved on page 3 of this paper.

*Rebutting the Sipser Halting Problem Proof*
https://www.researchgate.net/publication/364302709_Rebutting_the_Sipser_Halting_Problem_Proof
*Still no rebuttal of page 3 because you know that page 3 is >>>>>>>>>> correct*

You still seem to think that because you have an H that
partially computes the PO-halting function that it has
anything to do with the halting function. It does not.

So anything that does not address whether the halting
function is computable is irrelevant.

Anyone that is sufficiently technically competent can verify
that H does correctly determine the halt status of D correctly >>>>>>>> simulated by H.

No one is denying that you're able to compute a subset of the
PO-halting function. The halting problem proofs are about the
halting function.

This proves that the conventional proofs that rely on D doing
the opposite of whatever H decides have been refuted by the
notion of a simulating halt decider.

The conventional proofs are making claims about the halting
function, not the PO-halting function, therefore claims about
the PO-halting function are irrelevant.

[ repeat of previously refuted statement ]

int Sipser_D(int (*M)())
{
if ( Sipser_H(M, M) )
return 0;
return 1;
}
This notion of a simulating halt decider is proven to correctly
determine the halt status of Sipser_D by Sipser_H.
*Rebutting the Sipser Halting Problem Proof*
https://www.researchgate.net/publication/364302709_Rebutting_the_Sipser_Halting_Problem_Proof

In other words, you can compute a subset of the PO-halting
function. And since the halting problem proofs make claims about
the halting function, claims about the PO-halting function are
irrelevant.

The halting problem proofs make claims about the halting function
on the basis that the halt status of Sipser_D cannot be correctly
determined by Sipser_H.

Correct: the halting function maps D to halting but Sipser_H maps D
to non-halting, so it is unable to compute the halting function.

*Professor Sipser has agreed to these verbatim words* (and no more)
If simulating halt decider H correctly simulates its input D until H
correctly determines that its simulated D would never stop running
unless aborted then H can abort its simulation of D and correctly
report that D specifies a non-halting sequence of configurations.

Thus professor Sipser has agreed that the above H does compute the
halting function for the above D.

Professor Sipser has specifically approved the abstract to this paper:

*Rebutting the Sipser Halting Problem Proof*
https://www.researchgate.net/publication/364302709_Rebutting_the_Sipser_Halting_Problem_Proof

If H is a Flibble Signaling Decider then H will correctly simulate its
input D however if H is an Olcott Simulation Detector H will not
correctly simulate its input D as the only correct simulation of D is
for the simulation to behave as if D(D) was directly executed.

/Flibble

On 10/17/2022 10:23 AM, Ben Bacarisse wrote:

...D(D) would not halt unless H stops the simulation.
H /can/ correctly determine this silly criterion
(in this one case)...

*Professor Sipser has agreed to these verbatim words* (and no more)
If simulating halt decider H correctly simulates its input D until H
correctly determines that its simulated D would never stop running
unless aborted then H can abort its simulation of D and correctly report
that D specifies a non-halting sequence of configurations.

Thus it seems to me (I may be wrong) that Ben agrees that when the
Sipser approved criteria are applied that Sipser_H does correctly
determine the halt status of Sipser_D.

--
Copyright 2022 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)