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.