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: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.
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:
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.On Monday, October 17, 2022 at 11:44:10 AM UTC-4, olcott wrote: >>>>>>>>>> On 10/17/2022 10:40 AM, Dennis Bush wrote:Anyone that is sufficiently technically competent can verify that H does
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:*The PO-halting function is now Sipser approved*
On Monday, October 17, 2022 at 10:38:09 AM UTC-4, olcott wrote: >>>>>>>>>>>>>>>> On 10/17/2022 7:47 AM, Dennis Bush wrote:I have proven an exception to this rule:
And he agreed to those words based on their commonly known meanings, not your alternate weasel-word meanings.On Monday, October 17, 2022 at 5:30:59 AM UTC-4, Fred. Zwarts wrote:*Professor Sipser has agreed to these verbatim words* (and no more)
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.
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. >>>>>>>>>>>>>>>
The conventional definition of "correctly simulating" means that the simulated behavior EXACTLY matches the behavior of direct execution.
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:
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.
correctly determine the halt status of D correctly simulated by H. >>>>>>>
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.
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.
...D(D) would not halt unless H stops the simulation.
H /can/ correctly determine this silly criterion
(in this one case)...
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:The halting problem proofs make claims about the halting function
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, olcottAnyone that is sufficiently technically competent can verify
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:*The PO-halting function is now Sipser approved*
On 10/17/2022 9:49 AM, Dennis Bush wrote:
On Monday, October 17, 2022 at 10:38:09 AM UTC-4, >>>>>>>>>>>>>>> olcott wrote:I have proven an exception to this rule:
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:*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.
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.
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.
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:
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.
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.
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
...D(D) would not halt unless H stops the simulation.
H /can/ correctly determine this silly criterion
(in this one case)...
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: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.
On Monday, October 17, 2022 at 11:57:18 AM UTC-4, olcott wrote: >>>>>>>>>> On 10/17/2022 10:47 AM, Dennis Bush wrote:
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.On Monday, October 17, 2022 at 11:44:10 AM UTC-4, olcott wrote: >>>>>>>>>>>> On 10/17/2022 10:40 AM, Dennis Bush wrote:Anyone that is sufficiently technically competent can verify that H does
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:*The PO-halting function is now Sipser approved*
On Monday, October 17, 2022 at 10:38:09 AM UTC-4, olcott wrote:I have proven an exception to this rule:
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:And he agreed to those words based on their commonly known meanings, not your alternate weasel-word meanings.
*Professor Sipser has agreed to these verbatim words* (and no more)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.
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. >>>>>>>>>>>>>>>>>
The conventional definition of "correctly simulating" means that the simulated behavior EXACTLY matches the behavior of direct execution.
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:
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.
correctly determine the halt status of D correctly simulated by H. >>>>>>>>>
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.
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.
...D(D) would not halt unless H stops the simulation.
H /can/ correctly determine this silly criterion
(in this one case)...
[ repeat of previously refuted claim ]
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.
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.
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:The halting problem proofs make claims about the halting function on the
On Monday, October 17, 2022 at 11:57:18 AM UTC-4, olcott wrote: >>>>>>>>>>>> On 10/17/2022 10:47 AM, Dennis Bush wrote:
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.On Monday, October 17, 2022 at 11:44:10 AM UTC-4, olcott wrote: >>>>>>>>>>>>>> On 10/17/2022 10:40 AM, Dennis Bush wrote:Anyone that is sufficiently technically competent can verify that H does
On Monday, October 17, 2022 at 11:31:41 AM UTC-4, olcott wrote: >>>>>>>>>>>>>>>> On 10/17/2022 10:16 AM, Dennis Bush wrote:
No it's not, because he used the actual meaning of the words and not your weasel-worded definitions. Using the real definitions,On Monday, October 17, 2022 at 11:06:45 AM UTC-4, olcott wrote:*The PO-halting function is now Sipser approved* >>>>>>>>>>>>>>>
On 10/17/2022 9:49 AM, Dennis Bush wrote: >>>>>>>>>>>>>>>>>>> On Monday, October 17, 2022 at 10:38:09 AM UTC-4, olcott wrote:
I have proven an exception to this rule: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:And he agreed to those words based on their commonly known meanings, not your alternate weasel-word meanings.
*Professor Sipser has agreed to these verbatim words* (and no more)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.
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. >>>>>>>>>>>>>>>>>>>
The conventional definition of "correctly simulating" means that the simulated behavior EXACTLY matches the behavior of direct execution.
That's not a rule. It's a definition.
So in other words your Sipser_H is computing the PO-halting function:
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. >>>>>>>>>>>>>>>>>
*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.
correctly determine the halt status of D correctly simulated by H. >>>>>>>>>>>
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.
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.
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:The halting problem proofs make claims about the halting function on the
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:Anyone that is sufficiently technically competent can verify that H does
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:No it's not, because he used the actual meaning of the words and not your weasel-worded definitions. Using the real definitions,
*The PO-halting function is now Sipser approved* >>>>>>>>>>>>>>>>>On 10/17/2022 9:49 AM, Dennis Bush wrote: >>>>>>>>>>>>>>>>>>>>> On Monday, October 17, 2022 at 10:38:09 AM UTC-4, olcott wrote:That's not a rule. It's a definition.
I have proven an exception to this rule: >>>>>>>>>>>>>>>>>>>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:
*Professor Sipser has agreed to these verbatim words* (and no more)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.
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.
So in other words your Sipser_H is computing the PO-halting function:
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. >>>>>>>>>>>>>>>>>>>
*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.
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.
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.
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:Because a simulating halt decider does not exactly match the notion of a
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:The halting problem proofs make claims about the halting function on the
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:Anyone that is sufficiently technically competent can verify that H does
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:No it's not, because he used the actual meaning of the words and not your weasel-worded definitions. Using the real definitions,
*The PO-halting function is now Sipser approved* >>>>>>>>>>>>>>>>>>>On 10/17/2022 9:49 AM, Dennis Bush wrote: >>>>>>>>>>>>>>>>>>>>>>> On Monday, October 17, 2022 at 10:38:09 AM UTC-4, olcott wrote:That's not a rule. It's a definition. >>>>>>>>>>>>>>>>>>>>>
I have proven an exception to this rule: >>>>>>>>>>>>>>>>>>>>>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:
*Professor Sipser has agreed to these verbatim words* (and no more)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.
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.
So in other words your Sipser_H is computing the PO-halting function:
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. >>>>>>>>>>>>>>>>>>>>>
*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.
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.
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.
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.
On Monday, October 17, 2022 at 6:41:49 PM UTC-4, olcott wrote:
On 10/17/2022 4:50 PM, Dennis Bush wrote:
On Monday, October 17, 2022 at 5:37:30 PM UTC-4, olcott wrote:Yes everyone that learns by rote and has no depth of understanding would
On 10/17/2022 1:55 PM, Dennis Bush wrote:
On Monday, October 17, 2022 at 2:20:15 PM UTC-4, olcott wrote:Because a simulating halt decider does not exactly match the notion of a >>>> halt decider found is textbooks
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:The halting problem proofs make claims about the halting function on the
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:
Anyone that is sufficiently technically competent can verify that H doesOn 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:No it's not, because he used the actual meaning of the words and not your weasel-worded definitions. Using the real definitions,
*The PO-halting function is now Sipser approved* >>>>>>>>>>>>>>>>>>>>>On 10/17/2022 9:49 AM, Dennis Bush wrote: >>>>>>>>>>>>>>>>>>>>>>>>> On Monday, October 17, 2022 at 10:38:09 AM UTC-4, olcott wrote:That's not a rule. It's a definition. >>>>>>>>>>>>>>>>>>>>>>>
I have proven an exception to this rule: >>>>>>>>>>>>>>>>>>>>>>>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:
*Professor Sipser has agreed to these verbatim words* (and no more)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.
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.
So in other words your Sipser_H is computing the PO-halting function:
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. >>>>>>>>>>>>>>>>>>>>>>>
*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.
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.
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.
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.
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.
FALSE. A simulating halt decider maps a subset of the PO-Halting function:
For a function X with input Y and a function H which simulates X: POH(H,X,Y)==1 if and only if there exists an implementation of H that can simulate X(Y) to completion
POH(H,X,Y)==0 if and only if there does not exist an implementation of H that can simulate X(Y) to completion
Hx is a PO-halt decider if and only if Hx(X,Y) == POH(Hx,X,Y)
While a halt decider maps 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
These are clearly different functions that don't even have the same number of 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.
In other words, a simulating halt decider is not a halt decider because it doesn't map 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
And is therefore irrelevant to the halting problem.
On Monday, October 17, 2022 at 7:42:29 PM UTC-4, olcott wrote:*Unless this "different" question is determined to be equivalent* Learned-by-rote people have no way to assess equivalence.
On 10/17/2022 5:46 PM, Dennis Bush wrote:
On Monday, October 17, 2022 at 6:41:49 PM UTC-4, olcott wrote:Sure and like I already said anyone that only learns-by-rote has no
On 10/17/2022 4:50 PM, Dennis Bush wrote:FALSE. A simulating halt decider maps a subset of the PO-Halting function: >>>
On Monday, October 17, 2022 at 5:37:30 PM UTC-4, olcott wrote: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.
On 10/17/2022 1:55 PM, Dennis Bush wrote:
On Monday, October 17, 2022 at 2:20:15 PM UTC-4, olcott wrote:Because a simulating halt decider does not exactly match the notion of a >>>>>> halt decider found is textbooks
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:The halting problem proofs make claims about the halting function on the
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:
Anyone that is sufficiently technically competent can verify that H doesOn 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:No it's not, because he used the actual meaning of the words and not your weasel-worded definitions. Using the real definitions,
*The PO-halting function is now Sipser approved* >>>>>>>>>>>>>>>>>>>>>>>On 10/17/2022 9:49 AM, Dennis Bush wrote: >>>>>>>>>>>>>>>>>>>>>>>>>>> On Monday, October 17, 2022 at 10:38:09 AM UTC-4, olcott wrote:That's not a rule. It's a definition. >>>>>>>>>>>>>>>>>>>>>>>>>
I have proven an exception to this rule: >>>>>>>>>>>>>>>>>>>>>>>>>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:
*Professor Sipser has agreed to these verbatim words* (and no more)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.
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.
So in other words your Sipser_H is computing the PO-halting function:
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. >>>>>>>>>>>>>>>>>>>>>>>>>
*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.
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.
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.
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.
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. >>>
For a function X with input Y and a function H which simulates X:
POH(H,X,Y)==1 if and only if there exists an implementation of H that can simulate X(Y) to completion
POH(H,X,Y)==0 if and only if there does not exist an implementation of H that can simulate X(Y) to completion
Hx is a PO-halt decider if and only if Hx(X,Y) == POH(Hx,X,Y)
While a halt decider maps 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
These are clearly different functions that don't even have the same number of 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.
In other words, a simulating halt decider is not a halt decider because it doesn't map 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
And is therefore irrelevant to the halting problem.
basis to evaluate this differently.
Because professor Sipser knows these things much deeper than by rote
memorization he can correctly evaluate cases where the learned-by-rote
definition can be correctly adapted.
Answering a different question doesn't make the original question go away.
On 10/17/2022 6:51 PM, Dennis Bush wrote:
Answering a different question doesn't make the original question go*Unless this "different" question is determined to be equivalent* Learned-by-rote people have no way to assess equivalence.
away.
| Sysop: | Keyop |
|---|---|
| Location: | Huddersfield, West Yorkshire, UK |
| Users: | 297 |
| Nodes: | 16 (0 / 16) |
| Uptime: | 126:36:43 |
| Calls: | 6,663 |
| Calls today: | 1 |
| Files: | 12,212 |
| Messages: | 5,334,958 |