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.
>

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