On 10/17/2022 4:50 PM, Dennis Bush wrote:
> On Monday, October 17, 2022 at 5:37:30 PM UTC-4, olcott wrote:
>> On 10/17/2022 1:55 PM, Dennis Bush wrote:
>>> On Monday, October 17, 2022 at 2:20:15 PM UTC-4, olcott wrote:
>>>> On 10/17/2022 12:57 PM, Dennis Bush wrote:
>>>>> On Monday, October 17, 2022 at 1:33:57 PM UTC-4, olcott wrote:
>>>>>> On 10/17/2022 12:13 PM, Dennis Bush wrote:
>>>>>>> On Monday, October 17, 2022 at 1:08:42 PM UTC-4, olcott wrote:
>>>>>>>> On 10/17/2022 11:51 AM, Dennis Bush wrote:
>>>>>>>>> On Monday, October 17, 2022 at 12:42:25 PM UTC-4, olcott 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.
>>>>>>>>>>
>>>>>>>>>> [ repeat of previously refuted statement ]
>>>>>>>>>>
>>>>>>>>>> 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
>>>>>>>>>
>>>>>>>>> Claims about the PO-halting function are irrelevant to claims about the computability of the halting function. Answering a different question doesn't make the original question answerable.
>>>>>>>>>
>>>>>>
>>>>>> [ repeat of previously refuted statement ]
>>>>>>>
>>>>>>> It's determining the PO-halt status (i.e. mapping the PO-halting function), not the halt status (i.e. mapping the halting function).
>>>>>>>
>>>>>>> The halting problem proofs only care about the latter, so the former is irrelevant.
>>>>>>
>>>>>> [ repeat of previously refuted statement ]
>>>>>
>>>>> The halting problem proofs state that the halting function:
>>>>>
>>>>> 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
>>>>>
>>>>> Is not a computable function, therefore claims about the PO-halting function are irrelevant.
>>>>
>>>> [ repeat of previously refuted statement ]
>>>>
>>>> That prior work in this field totally ignored the notion of a simulating
>>>> halt decider
>>>
>>> Because a simulating halt decider is not a halt decider since it maps a subset the PO-halting function instead of the halting function.
>>>
>> Because a simulating halt decider does not exactly match the notion of a
>> halt decider found is textbooks
>
> It therefore has no relevance to the halting problem, as the halting problem is about whether the halting function:
>
> 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
>
> Is a computable function.

Yes everyone that learns by rote and has no depth of understanding would
agree with that because the notion of a simulating halt decider has been
ignored by all of the textbooks in the field.

A simulating halt decider (SHD) correctly maps its finite string inputs
to an accept or reject state on the basis of the actual behavior
specified by this finite string as measured by its correct simulation of
this finite string, THUS IS NECESSARILY A HALT DECIDER FOR THESE INPUTS.

A SHD maps all of its inputs to the same accept or reject state that any
other halt decider would map to except for the conventional "impossible"
inputs.

--
Copyright 2022 Pete Olcott "Talent hits a target no one else can hit;
Genius hits a target no one else can see." Arthur Schopenhauer