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.)
On 2022-10-17 09:30:56 +0000, Fred. Zwarts said:
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'.)
Definitions vary a little among authors. Usually the halting problem and other computability problems define that "program" is a Turing machine.
The exact definition of "halt" varies but often it means that the execution has reached a situation where there is no rule specifying what to do next. With other definitions one must check whether it is possible that the execution neither halts nor runs forever.
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.)
The halt decider must be a program in the same sense as the programs it examines are programs. Usually the requirement is that the required halt decider is a Turing machine and its input is a description of a Turing machine.
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'.)
Another way to say the same is that H is not a halt decider
if there is some X and some Y such that
- X(Y) halts and H(X,Y) returns 0
- X(Y) does not halt and H(X,Y) returns 1
- H(X,Y) returns something that is neither 0 nor 1
- H(X,Y) does not return anything
Paradoxical program:
Also called "pathological 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.)
All that is correct.
Mikko
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.
On Monday, 17 October 2022 at 17:30:59 UTC+8, 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'.)
Basically, yes. The HP (most formal one) is specified using TM.
A TM halts means it reaches designated final state. This is equivalent to a program 'returns' (whatever, you define the 'final state').
OTHER conditions are non-halting.
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.)
I find it not quite simple to define 'halt decider', probably not necessary. So, I say any program X that tries to test whether a given program (as X's input)
halts or not is a 'halt decider'.
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'.)
Yes, according to the definition (a failed halt decider)
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'.)
Yes, according to the definition (a failed halt decider)
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:
There are many details, but yes, you are correct.
6) If P(P) halts, then H should return 1, but if H would do so, P(P)
would not halt.
Correct.
7) If P(P) does not halt, H should return 0, but if H would do so, P(P)
would halt.
Correct.
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.)
H is not the halt decider the Halting Problem specifies (a failed halt decider).
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)
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.
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: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: >>>>>> 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?*Professor Sipser has agreed to these verbatim words* (and no more)
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.
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:
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: >>>>>>>> I have been following the discussions about Halt deciders with interest.*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.
As a retired software designer and developer, I have a lot of practicalYour understanding is correct. To sum things up, the halting function (using the mathematical notion of a function), performs the following mapping:
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.) >>>>>>>
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,
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:*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: >>>>>>>> On 10/17/2022 7:47 AM, Dennis Bush wrote:I have proven an exception to this rule:
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.*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
As a retired software designer and developer, I have a lot of practicalYour understanding is correct. To sum things up, the halting function (using the mathematical notion of a function), performs the following mapping:
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.) >>>>>>>>>
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.
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.
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.
On 17/10/2022 13:43, Mikko wrote:
{Fred. Zwarts:]
Paradoxical program:Also called "pathological program"
Just an additional comment. The use of words such as "paradoxical", "pathological", "impossible", ... conveys to the
unwary reader a notion that these programs are difficult, or
unreasonable, in some way. Not so; they are merely counter-
examples. *If* you claim to have a program "H" that [you claim]
is a "halt decider", *then*, sorry, your claim is incorrect, and
/here/ is a program "P" on which "H" fails [where "here" denotes
the standard "do the opposite" construction much discussed here].
On 10/17/2022 11:25 AM, Dennis Bush wrote:...
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. The notion of a simulating halt decider removes that basis
thus causing all of these conventional proofs to fail.
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: >>>>>>>> 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:
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
I have been following the discussions about Halt deciders with interest.Your understanding is correct. To sum things up, the halting function (using the mathematical notion of a function), performs the following mapping:
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.) >>>>>>>>>>>
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.
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.
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.
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.
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:Anyone that is sufficiently technically competent can verify that H does >>>> correctly determine the halt status of D correctly simulated by H.
On 10/17/2022 10:40 AM, Dennis Bush wrote: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.
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* >>>>>
So anything that does not address whether the halting function is computable is irrelevant.
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 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: >>>>>>>> On 10/17/2022 10:40 AM, Dennis Bush wrote:Anyone that is sufficiently technically competent can verify that H does >>>>>> correctly determine the halt status of D correctly simulated by H.
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.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* >>>>>>>
So anything that does not address whether the halting function is computable is irrelevant.
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.
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,I have proven an exception to this rule:
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:*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
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.
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.
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
On 10/17/2022 4:30 AM, 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.)
*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.
An alternative definition for a halt decider approved by MIT Professor Michael Sipser (author of the best selling book on the theory of
computation) https://www.amazon.com/Introduction-Theory-Computation-Sipser/dp/8131525295 is shown above and paraphrased below:
Would D correctly simulated by H ever stop running if not aborted?
Is proven on page 3 of this paper to be "no" thus perfectly meeting the Sipser approved criteria shown above.
*Rebutting the Sipser Halting Problem Proof* https://www.researchgate.net/publication/364302709_Rebutting_the_Sipser_Halting_Problem_Proof
Op 17.okt..2022 om 16:29 schreef olcott:
On 10/17/2022 4:30 AM, 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.)
*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.
An alternative definition for a halt decider approved by MIT Professor Michael Sipser (author of the best selling book on the theory of computation)
https://www.amazon.com/Introduction-Theory-Computation-Sipser/dp/8131525295 is shown above and paraphrased below:
Would D correctly simulated by H ever stop running if not aborted?
Is proven on page 3 of this paper to be "no" thus perfectly meeting the Sipser approved criteria shown above.
*Rebutting the Sipser Halting Problem Proof*
https://www.researchgate.net/publication/364302709_Rebutting_the_Sipser_Halting_Problem_Proof
It is not clear to me what you want to say and why you left out my other points from the quote. You quote only the definitions. You left out the points
that follow from the definitions. What does that mean. Don't you agree with the definitions, or is something wrong with the other points?
Op 17.okt..2022 om 16:29 schreef olcott:
On 10/17/2022 4:30 AM, 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.)
*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.
An alternative definition for a halt decider approved by MIT Professor
Michael Sipser (author of the best selling book on the theory of
computation)
https://www.amazon.com/Introduction-Theory-Computation-Sipser/dp/8131525295 is shown above and paraphrased below:
Would D correctly simulated by H ever stop running if not aborted?
Is proven on page 3 of this paper to be "no" thus perfectly meeting
the Sipser approved criteria shown above.
*Rebutting the Sipser Halting Problem Proof*
https://www.researchgate.net/publication/364302709_Rebutting_the_Sipser_Halting_Problem_Proof
It is not clear to me what you want to say and why you left out my other points from the quote. You quote only the definitions. You left out the points that follow from the definitions. What does that mean. Don't you
agree with the definitions, or is something wrong with the other points?
On 10/17/2022 1:44 PM, Fred. Zwarts wrote:
Op 17.okt..2022 om 16:29 schreef olcott:
On 10/17/2022 4:30 AM, 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.)
*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.
An alternative definition for a halt decider approved by MIT
Professor Michael Sipser (author of the best selling book on the
theory of computation)
https://www.amazon.com/Introduction-Theory-Computation-Sipser/dp/8131525295 is shown above and paraphrased below:
Would D correctly simulated by H ever stop running if not aborted?
Is proven on page 3 of this paper to be "no" thus perfectly meeting
the Sipser approved criteria shown above.
*Rebutting the Sipser Halting Problem Proof*
https://www.researchgate.net/publication/364302709_Rebutting_the_Sipser_Halting_Problem_Proof
It is not clear to me what you want to say and why you left out my
other points from the quote. You quote only the definitions. You left
out the points that follow from the definitions. What does that mean.
Don't you agree with the definitions, or is something wrong with the
other points?
*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.
Because the above seems to agree with my definition of a simulating halt decider other definitions that do not apply to simulating halt deciders
are irrelevant.
If I claim that a boat can transport you across the water of a lake to
the other side when someone claims that I am wrong because an automobile cannot transport you across the water of a lake this is the strawman error.
Op 17.okt..2022 om 23:22 schreef olcott:
On 10/17/2022 1:44 PM, Fred. Zwarts wrote:
Op 17.okt..2022 om 16:29 schreef olcott:
On 10/17/2022 4:30 AM, 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.)
*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.
An alternative definition for a halt decider approved by MIT
Professor Michael Sipser (author of the best selling book on the
theory of computation)
https://www.amazon.com/Introduction-Theory-Computation-Sipser/dp/8131525295 is shown above and paraphrased below:
Would D correctly simulated by H ever stop running if not aborted?
Is proven on page 3 of this paper to be "no" thus perfectly meeting
the Sipser approved criteria shown above.
*Rebutting the Sipser Halting Problem Proof*
https://www.researchgate.net/publication/364302709_Rebutting_the_Sipser_Halting_Problem_Proof
It is not clear to me what you want to say and why you left out my
other points from the quote. You quote only the definitions. You left
out the points that follow from the definitions. What does that mean.
Don't you agree with the definitions, or is something wrong with the
other points?
*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.
Because the above seems to agree with my definition of a simulating
halt decider other definitions that do not apply to simulating halt
deciders are irrelevant.
I was not talking about simulating halt deciders, but about halt
deciders. Since we seem to agree that they are not the same, I have to conclude that your contribution is irrelevant.
If I claim that a boat can transport you across the water of a lake to
the other side when someone claims that I am wrong because an
automobile cannot transport you across the water of a lake this is the
strawman error.
If I claim that an automobile is unable to cross the water, then your
remark that a boat can do it, is irrelevant.
Trying to deny it is dangerous, because then people could try to cross
the water with a automobile.
Op 18.okt..2022 om 17:02 schreef olcott:
On 10/18/2022 3:17 AM, Fred. Zwarts wrote:
Op 17.okt..2022 om 23:22 schreef olcott:
On 10/17/2022 1:44 PM, Fred. Zwarts wrote:
Op 17.okt..2022 om 16:29 schreef olcott:
On 10/17/2022 4:30 AM, 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.)
*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.
An alternative definition for a halt decider approved by MIT
Professor Michael Sipser (author of the best selling book on the
theory of computation)
https://www.amazon.com/Introduction-Theory-Computation-Sipser/dp/8131525295 is shown above and paraphrased below:
Would D correctly simulated by H ever stop running if not aborted? >>>>>> Is proven on page 3 of this paper to be "no" thus perfectly
meeting the Sipser approved criteria shown above.
*Rebutting the Sipser Halting Problem Proof*
https://www.researchgate.net/publication/364302709_Rebutting_the_Sipser_Halting_Problem_Proof
It is not clear to me what you want to say and why you left out my
other points from the quote. You quote only the definitions. You
left out the points that follow from the definitions. What does
that mean. Don't you agree with the definitions, or is something
wrong with the other points?
*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.
Because the above seems to agree with my definition of a simulating
halt decider other definitions that do not apply to simulating halt
deciders are irrelevant.
I was not talking about simulating halt deciders, but about halt
deciders. Since we seem to agree that they are not the same, I have
to conclude that your contribution is irrelevant.
That is the same as saying that airplanes do not fly because cars do
not fly and we were talking about cars.
If we are talking about cars, it is irrelevant to change the subject to airplanes.
But if you think your car is an airplane, it is dangerous to try to fly
with it.
On 10/18/2022 3:17 AM, Fred. Zwarts wrote:
Op 17.okt..2022 om 23:22 schreef olcott:
On 10/17/2022 1:44 PM, Fred. Zwarts wrote:
Op 17.okt..2022 om 16:29 schreef olcott:
On 10/17/2022 4:30 AM, 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.)
*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.
An alternative definition for a halt decider approved by MIT
Professor Michael Sipser (author of the best selling book on the
theory of computation)
https://www.amazon.com/Introduction-Theory-Computation-Sipser/dp/8131525295 is shown above and paraphrased below:
Would D correctly simulated by H ever stop running if not aborted?
Is proven on page 3 of this paper to be "no" thus perfectly meeting
the Sipser approved criteria shown above.
*Rebutting the Sipser Halting Problem Proof*
https://www.researchgate.net/publication/364302709_Rebutting_the_Sipser_Halting_Problem_Proof
It is not clear to me what you want to say and why you left out my
other points from the quote. You quote only the definitions. You
left out the points that follow from the definitions. What does that
mean. Don't you agree with the definitions, or is something wrong
with the other points?
*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.
Because the above seems to agree with my definition of a simulating
halt decider other definitions that do not apply to simulating halt
deciders are irrelevant.
I was not talking about simulating halt deciders, but about halt
deciders. Since we seem to agree that they are not the same, I have to
conclude that your contribution is irrelevant.
That is the same as saying that airplanes do not fly because cars do not
fly and we were talking about cars.
On 10/18/2022 2:23 PM, Fred. Zwarts wrote:
Op 18.okt..2022 om 17:02 schreef olcott:
On 10/18/2022 3:17 AM, Fred. Zwarts wrote:
Op 17.okt..2022 om 23:22 schreef olcott:
On 10/17/2022 1:44 PM, Fred. Zwarts wrote:
Op 17.okt..2022 om 16:29 schreef olcott:
On 10/17/2022 4:30 AM, 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.)
*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.
An alternative definition for a halt decider approved by MIT
Professor Michael Sipser (author of the best selling book on the >>>>>>> theory of computation)
https://www.amazon.com/Introduction-Theory-Computation-Sipser/dp/8131525295 is shown above and paraphrased below:
Would D correctly simulated by H ever stop running if not aborted? >>>>>>> Is proven on page 3 of this paper to be "no" thus perfectly
meeting the Sipser approved criteria shown above.
*Rebutting the Sipser Halting Problem Proof*
https://www.researchgate.net/publication/364302709_Rebutting_the_Sipser_Halting_Problem_Proof
It is not clear to me what you want to say and why you left out my >>>>>> other points from the quote. You quote only the definitions. You
left out the points that follow from the definitions. What does
that mean. Don't you agree with the definitions, or is something
wrong with the other points?
*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.
Because the above seems to agree with my definition of a simulating
halt decider other definitions that do not apply to simulating halt
deciders are irrelevant.
I was not talking about simulating halt deciders, but about halt
deciders. Since we seem to agree that they are not the same, I have
to conclude that your contribution is irrelevant.
That is the same as saying that airplanes do not fly because cars do
not fly and we were talking about cars.
If we are talking about cars, it is irrelevant to change the subject
to airplanes.
But if you think your car is an airplane, it is dangerous to try to
fly with it.
*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.
Seems to be saying that a simulating halt decider does correctly
determine the halt status of its input.
The only requirement for a halt decider is that it does correctly
determine the halt status of its inputs.
Op 18.okt..2022 om 21:46 schreef olcott:
On 10/18/2022 2:23 PM, Fred. Zwarts wrote:
Op 18.okt..2022 om 17:02 schreef olcott:
On 10/18/2022 3:17 AM, Fred. Zwarts wrote:
Op 17.okt..2022 om 23:22 schreef olcott:
On 10/17/2022 1:44 PM, Fred. Zwarts wrote:
Op 17.okt..2022 om 16:29 schreef olcott:
On 10/17/2022 4:30 AM, 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.)
*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.
An alternative definition for a halt decider approved by MIT
Professor Michael Sipser (author of the best selling book on the >>>>>>>> theory of computation)
https://www.amazon.com/Introduction-Theory-Computation-Sipser/dp/8131525295 is shown above and paraphrased below:
Would D correctly simulated by H ever stop running if not aborted? >>>>>>>> Is proven on page 3 of this paper to be "no" thus perfectly
meeting the Sipser approved criteria shown above.
*Rebutting the Sipser Halting Problem Proof*
https://www.researchgate.net/publication/364302709_Rebutting_the_Sipser_Halting_Problem_Proof
It is not clear to me what you want to say and why you left out
my other points from the quote. You quote only the definitions.
You left out the points that follow from the definitions. What
does that mean. Don't you agree with the definitions, or is
something wrong with the other points?
*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.
Because the above seems to agree with my definition of a
simulating halt decider other definitions that do not apply to
simulating halt deciders are irrelevant.
I was not talking about simulating halt deciders, but about halt
deciders. Since we seem to agree that they are not the same, I have
to conclude that your contribution is irrelevant.
That is the same as saying that airplanes do not fly because cars do
not fly and we were talking about cars.
If we are talking about cars, it is irrelevant to change the subject
to airplanes.
But if you think your car is an airplane, it is dangerous to try to
fly with it.
*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.
Seems to be saying that a simulating halt decider does correctly
determine the halt status of its input.
The only requirement for a halt decider is that it does correctly
determine the halt status of its inputs.
I started this thread with a question about Halt Deciders. I included a definition (see above). Why do you keep changing the subject to things
with other definitions? Cars, airplanes, simulating halt deciders,
boats, automobiles? Please, stay at the subject.
On 10/19/2022 11:43 AM, Fred. Zwarts wrote:
Op 18.okt..2022 om 21:46 schreef olcott:
On 10/18/2022 2:23 PM, Fred. Zwarts wrote:
Op 18.okt..2022 om 17:02 schreef olcott:
On 10/18/2022 3:17 AM, Fred. Zwarts wrote:
Op 17.okt..2022 om 23:22 schreef olcott:
On 10/17/2022 1:44 PM, Fred. Zwarts wrote:
Op 17.okt..2022 om 16:29 schreef olcott:
On 10/17/2022 4:30 AM, 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.)
*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.
An alternative definition for a halt decider approved by MIT >>>>>>>>> Professor Michael Sipser (author of the best selling book on >>>>>>>>> the theory of computation)
https://www.amazon.com/Introduction-Theory-Computation-Sipser/dp/8131525295 is shown above and paraphrased below:
Would D correctly simulated by H ever stop running if not aborted? >>>>>>>>> Is proven on page 3 of this paper to be "no" thus perfectly
meeting the Sipser approved criteria shown above.
*Rebutting the Sipser Halting Problem Proof*
https://www.researchgate.net/publication/364302709_Rebutting_the_Sipser_Halting_Problem_Proof
It is not clear to me what you want to say and why you left out >>>>>>>> my other points from the quote. You quote only the definitions. >>>>>>>> You left out the points that follow from the definitions. What >>>>>>>> does that mean. Don't you agree with the definitions, or is
something wrong with the other points?
*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.
Because the above seems to agree with my definition of a
simulating halt decider other definitions that do not apply to
simulating halt deciders are irrelevant.
I was not talking about simulating halt deciders, but about halt
deciders. Since we seem to agree that they are not the same, I
have to conclude that your contribution is irrelevant.
That is the same as saying that airplanes do not fly because cars
do not fly and we were talking about cars.
If we are talking about cars, it is irrelevant to change the subject
to airplanes.
But if you think your car is an airplane, it is dangerous to try to
fly with it.
*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.
Seems to be saying that a simulating halt decider does correctly
determine the halt status of its input.
The only requirement for a halt decider is that it does correctly
determine the halt status of its inputs.
I started this thread with a question about Halt Deciders. I included
a definition (see above). Why do you keep changing the subject to
things with other definitions? Cars, airplanes, simulating halt
deciders, boats, automobiles? Please, stay at the subject.
The above quote seems to say that a simulating halt decider does
correctly determine the halt status of the input that it simulates.
Professor Sipser is the author of the best selling book on the theory of computation would seem to have the knowledge required to approve
alternative definitions for halt deciders.
https://www.amazon.com/Introduction-Theory-Computation-Sipser/dp/8131525295
Only the notion of a simulating halt decider defeats the conventional HP proofs. To insist on definitions that cannot defeat these proofs seems a little silly.
Op 19.okt..2022 om 19:01 schreef olcott:
On 10/19/2022 11:43 AM, Fred. Zwarts wrote:
Op 18.okt..2022 om 21:46 schreef olcott:
On 10/18/2022 2:23 PM, Fred. Zwarts wrote:
Op 18.okt..2022 om 17:02 schreef olcott:
On 10/18/2022 3:17 AM, Fred. Zwarts wrote:
Op 17.okt..2022 om 23:22 schreef olcott:
On 10/17/2022 1:44 PM, Fred. Zwarts wrote:
Op 17.okt..2022 om 16:29 schreef olcott:
On 10/17/2022 4:30 AM, 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.)
*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. >>>>>>>>>>
An alternative definition for a halt decider approved by MIT >>>>>>>>>> Professor Michael Sipser (author of the best selling book on >>>>>>>>>> the theory of computation)
https://www.amazon.com/Introduction-Theory-Computation-Sipser/dp/8131525295 is shown above and paraphrased below:
Would D correctly simulated by H ever stop running if not
aborted?
Is proven on page 3 of this paper to be "no" thus perfectly >>>>>>>>>> meeting the Sipser approved criteria shown above.
*Rebutting the Sipser Halting Problem Proof*
https://www.researchgate.net/publication/364302709_Rebutting_the_Sipser_Halting_Problem_Proof
It is not clear to me what you want to say and why you left out >>>>>>>>> my other points from the quote. You quote only the definitions. >>>>>>>>> You left out the points that follow from the definitions. What >>>>>>>>> does that mean. Don't you agree with the definitions, or is
something wrong with the other points?
*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.
Because the above seems to agree with my definition of a
simulating halt decider other definitions that do not apply to >>>>>>>> simulating halt deciders are irrelevant.
I was not talking about simulating halt deciders, but about halt >>>>>>> deciders. Since we seem to agree that they are not the same, I
have to conclude that your contribution is irrelevant.
That is the same as saying that airplanes do not fly because cars
do not fly and we were talking about cars.
If we are talking about cars, it is irrelevant to change the
subject to airplanes.
But if you think your car is an airplane, it is dangerous to try to
fly with it.
*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.
Seems to be saying that a simulating halt decider does correctly
determine the halt status of its input.
The only requirement for a halt decider is that it does correctly
determine the halt status of its inputs.
I started this thread with a question about Halt Deciders. I included
a definition (see above). Why do you keep changing the subject to
things with other definitions? Cars, airplanes, simulating halt
deciders, boats, automobiles? Please, stay at the subject.
The above quote seems to say that a simulating halt decider does
correctly determine the halt status of the input that it simulates.
Professor Sipser is the author of the best selling book on the theory
of computation would seem to have the knowledge required to approve
alternative definitions for halt deciders.
https://www.amazon.com/Introduction-Theory-Computation-Sipser/dp/8131525295 >>
Only the notion of a simulating halt decider defeats the conventional
HP proofs. To insist on definitions that cannot defeat these proofs
seems a little silly.
So, your contribution is irrelevant, because you want to change
definitions and you cannot show any error in the 9 points I was asking
about.
Don't change the subject, please.
H correctly determines that its simulated D would never stop
Op 19.okt..2022 om 19:28 schreef olcott:
On 10/19/2022 12:13 PM, Fred. Zwarts wrote:
Op 19.okt..2022 om 19:01 schreef olcott:
On 10/19/2022 11:43 AM, Fred. Zwarts wrote:
Op 18.okt..2022 om 21:46 schreef olcott:
On 10/18/2022 2:23 PM, Fred. Zwarts wrote:
Op 18.okt..2022 om 17:02 schreef olcott:
On 10/18/2022 3:17 AM, Fred. Zwarts wrote:
Op 17.okt..2022 om 23:22 schreef olcott:
On 10/17/2022 1:44 PM, Fred. Zwarts wrote:
Op 17.okt..2022 om 16:29 schreef olcott:
On 10/17/2022 4:30 AM, 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.)
*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. >>>>>>>>>>>>
An alternative definition for a halt decider approved by MIT >>>>>>>>>>>> Professor Michael Sipser (author of the best selling book on >>>>>>>>>>>> the theory of computation)
https://www.amazon.com/Introduction-Theory-Computation-Sipser/dp/8131525295 is shown above and paraphrased below:
Would D correctly simulated by H ever stop running if not >>>>>>>>>>>> aborted?
Is proven on page 3 of this paper to be "no" thus perfectly >>>>>>>>>>>> meeting the Sipser approved criteria shown above.
*Rebutting the Sipser Halting Problem Proof*
https://www.researchgate.net/publication/364302709_Rebutting_the_Sipser_Halting_Problem_Proof
It is not clear to me what you want to say and why you left >>>>>>>>>>> out my other points from the quote. You quote only the
definitions. You left out the points that follow from the >>>>>>>>>>> definitions. What does that mean. Don't you agree with the >>>>>>>>>>> definitions, or is something wrong with the other points? >>>>>>>>>>>
*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. >>>>>>>>>>
Because the above seems to agree with my definition of a
simulating halt decider other definitions that do not apply to >>>>>>>>>> simulating halt deciders are irrelevant.
I was not talking about simulating halt deciders, but about
halt deciders. Since we seem to agree that they are not the
same, I have to conclude that your contribution is irrelevant. >>>>>>>>>
That is the same as saying that airplanes do not fly because
cars do not fly and we were talking about cars.
If we are talking about cars, it is irrelevant to change the
subject to airplanes.
But if you think your car is an airplane, it is dangerous to try >>>>>>> to fly with it.
*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.
Seems to be saying that a simulating halt decider does correctly
determine the halt status of its input.
The only requirement for a halt decider is that it does correctly
determine the halt status of its inputs.
I started this thread with a question about Halt Deciders. I
included a definition (see above). Why do you keep changing the
subject to things with other definitions? Cars, airplanes,
simulating halt deciders, boats, automobiles? Please, stay at the
subject.
The above quote seems to say that a simulating halt decider does
correctly determine the halt status of the input that it simulates.
Professor Sipser is the author of the best selling book on the
theory of computation would seem to have the knowledge required to
approve alternative definitions for halt deciders.
https://www.amazon.com/Introduction-Theory-Computation-Sipser/dp/8131525295
Only the notion of a simulating halt decider defeats the
conventional HP proofs. To insist on definitions that cannot defeat
these proofs seems a little silly.
So, your contribution is irrelevant, because you want to change
definitions and you cannot show any error in the 9 points I was
asking about.
Don't change the subject, please.
In computability theory, the halting problem is the problem of
determining, from a description of an arbitrary computer program and
an input, whether the program will finish running, or continue to run
forever. Alan Turing proved in 1936 that a general algorithm to solve
the halting problem for all possible program-input pairs cannot exist.
For any program H that might determine if programs halt, a
"pathological" program D, called with some input, can pass its own
source and its input to H and then specifically do the opposite of
what H predicts D will do. No H can exist that handles this case.
https://en.wikipedia.org/wiki/Halting_problem
H(D,D) correctly simulates its input D until H correctly determines
that its simulated D would never stop running unless aborted thus
exactly matching the Wikipedia definition of an H can that handles
this case.
Your H returns 0, but D halts. Again you changed the subject.
On 10/19/2022 12:13 PM, Fred. Zwarts wrote:
Op 19.okt..2022 om 19:01 schreef olcott:
On 10/19/2022 11:43 AM, Fred. Zwarts wrote:
Op 18.okt..2022 om 21:46 schreef olcott:
On 10/18/2022 2:23 PM, Fred. Zwarts wrote:
Op 18.okt..2022 om 17:02 schreef olcott:
On 10/18/2022 3:17 AM, Fred. Zwarts wrote:
Op 17.okt..2022 om 23:22 schreef olcott:
On 10/17/2022 1:44 PM, Fred. Zwarts wrote:
Op 17.okt..2022 om 16:29 schreef olcott:
On 10/17/2022 4:30 AM, 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.)
*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. >>>>>>>>>>>
An alternative definition for a halt decider approved by MIT >>>>>>>>>>> Professor Michael Sipser (author of the best selling book on >>>>>>>>>>> the theory of computation)
https://www.amazon.com/Introduction-Theory-Computation-Sipser/dp/8131525295 is shown above and paraphrased below:
Would D correctly simulated by H ever stop running if not >>>>>>>>>>> aborted?
Is proven on page 3 of this paper to be "no" thus perfectly >>>>>>>>>>> meeting the Sipser approved criteria shown above.
*Rebutting the Sipser Halting Problem Proof*
https://www.researchgate.net/publication/364302709_Rebutting_the_Sipser_Halting_Problem_Proof
It is not clear to me what you want to say and why you left >>>>>>>>>> out my other points from the quote. You quote only the
definitions. You left out the points that follow from the
definitions. What does that mean. Don't you agree with the >>>>>>>>>> definitions, or is something wrong with the other points?
*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.
Because the above seems to agree with my definition of a
simulating halt decider other definitions that do not apply to >>>>>>>>> simulating halt deciders are irrelevant.
I was not talking about simulating halt deciders, but about halt >>>>>>>> deciders. Since we seem to agree that they are not the same, I >>>>>>>> have to conclude that your contribution is irrelevant.
That is the same as saying that airplanes do not fly because cars >>>>>>> do not fly and we were talking about cars.
If we are talking about cars, it is irrelevant to change the
subject to airplanes.
But if you think your car is an airplane, it is dangerous to try
to fly with it.
*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.
Seems to be saying that a simulating halt decider does correctly
determine the halt status of its input.
The only requirement for a halt decider is that it does correctly
determine the halt status of its inputs.
I started this thread with a question about Halt Deciders. I
included a definition (see above). Why do you keep changing the
subject to things with other definitions? Cars, airplanes,
simulating halt deciders, boats, automobiles? Please, stay at the
subject.
The above quote seems to say that a simulating halt decider does
correctly determine the halt status of the input that it simulates.
Professor Sipser is the author of the best selling book on the theory
of computation would seem to have the knowledge required to approve
alternative definitions for halt deciders.
https://www.amazon.com/Introduction-Theory-Computation-Sipser/dp/8131525295 >>>
Only the notion of a simulating halt decider defeats the conventional
HP proofs. To insist on definitions that cannot defeat these proofs
seems a little silly.
So, your contribution is irrelevant, because you want to change
definitions and you cannot show any error in the 9 points I was asking
about.
Don't change the subject, please.
In computability theory, the halting problem is the problem of
determining, from a description of an arbitrary computer program and an input, whether the program will finish running, or continue to run
forever. Alan Turing proved in 1936 that a general algorithm to solve
the halting problem for all possible program-input pairs cannot exist.
For any program H that might determine if programs halt, a
"pathological" program D, called with some input, can pass its own
source and its input to H and then specifically do the opposite of what
H predicts D will do. No H can exist that handles this case. https://en.wikipedia.org/wiki/Halting_problem
H(D,D) correctly simulates its input D until H correctly determines that
its simulated D would never stop running unless aborted thus exactly
matching the Wikipedia definition of an H can that handles this case.
On Thu, 20 Oct 2022 14:58:01 -0500
olcott <polcott2@gmail.com> wrote:
On 10/20/2022 2:28 PM, Fred. Zwarts wrote:
Op 19.okt..2022 om 19:28 schreef olcott:
On 10/19/2022 12:13 PM, Fred. Zwarts wrote:
Op 19.okt..2022 om 19:01 schreef olcott:
On 10/19/2022 11:43 AM, Fred. Zwarts wrote:
Op 18.okt..2022 om 21:46 schreef olcott:
On 10/18/2022 2:23 PM, Fred. Zwarts wrote:
Op 18.okt..2022 om 17:02 schreef olcott:
On 10/18/2022 3:17 AM, Fred. Zwarts wrote:
Op 17.okt..2022 om 23:22 schreef olcott:
On 10/17/2022 1:44 PM, Fred. Zwarts wrote:
Op 17.okt..2022 om 16:29 schreef olcott:
On 10/17/2022 4:30 AM, 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.)
*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.
An alternative definition for a halt decider approved by >>>>>>>>>>>>>> MIT Professor Michael Sipser (author of the best selling >>>>>>>>>>>>>> book on the theory of computation)
https://www.amazon.com/Introduction-Theory-Computation-Sipser/dp/8131525295
is shown above and paraphrased below:
Would D correctly simulated by H ever stop running if >>>>>>>>>>>>>> not aborted?
Is proven on page 3 of this paper to be "no" thus
perfectly meeting the Sipser approved criteria shown >>>>>>>>>>>>>> above.
*Rebutting the Sipser Halting Problem Proof*
https://www.researchgate.net/publication/364302709_Rebutting_the_Sipser_Halting_Problem_Proof
It is not clear to me what you want to say and why you >>>>>>>>>>>>> left out my other points from the quote. You quote only >>>>>>>>>>>>> the definitions. You left out the points that follow from >>>>>>>>>>>>> the definitions. What does that mean. Don't you agree >>>>>>>>>>>>> with the definitions, or is something wrong with the >>>>>>>>>>>>> other points?
*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. >>>>>>>>>>>>
Because the above seems to agree with my definition of a >>>>>>>>>>>> simulating halt decider other definitions that do not
apply to simulating halt deciders are irrelevant.
I was not talking about simulating halt deciders, but about >>>>>>>>>>> halt deciders. Since we seem to agree that they are not the >>>>>>>>>>> same, I have to conclude that your contribution is
irrelevant.
That is the same as saying that airplanes do not fly because >>>>>>>>>> cars do not fly and we were talking about cars.
If we are talking about cars, it is irrelevant to change the >>>>>>>>> subject to airplanes.
But if you think your car is an airplane, it is dangerous to >>>>>>>>> try to fly with it.
*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.
Seems to be saying that a simulating halt decider does
correctly determine the halt status of its input.
The only requirement for a halt decider is that it does
correctly determine the halt status of its inputs.
I started this thread with a question about Halt Deciders. I
included a definition (see above). Why do you keep changing the
subject to things with other definitions? Cars, airplanes,
simulating halt deciders, boats, automobiles? Please, stay at
the subject.
The above quote seems to say that a simulating halt decider does
correctly determine the halt status of the input that it
simulates.
Professor Sipser is the author of the best selling book on the
theory of computation would seem to have the knowledge required
to approve alternative definitions for halt deciders.
https://www.amazon.com/Introduction-Theory-Computation-Sipser/dp/8131525295
Only the notion of a simulating halt decider defeats the
conventional HP proofs. To insist on definitions that cannot
defeat these proofs seems a little silly.
So, your contribution is irrelevant, because you want to change
definitions and you cannot show any error in the 9 points I was
asking about.
Don't change the subject, please.
In computability theory, the halting problem is the problem of
determining, from a description of an arbitrary computer program
and an input, whether the program will finish running, or continue
to run forever. Alan Turing proved in 1936 that a general
algorithm to solve the halting problem for all possible
program-input pairs cannot exist.
For any program H that might determine if programs halt, a
"pathological" program D, called with some input, can pass its own
source and its input to H and then specifically do the opposite of
what H predicts D will do. No H can exist that handles this case.
https://en.wikipedia.org/wiki/Halting_problem
H(D,D) correctly simulates its input D until H correctly
determines that its simulated D would never stop running unless
aborted thus exactly matching the Wikipedia definition of an H can
that handles this case.
Your H returns 0, but D halts. Again you changed the subject.
You continue to look for a black dog in the kitchen by looking for a
white cat in the living room because you only understand these things
on the basis of learned-by-rote.
That the behavior of the input D correctly simulated by H is
validated as the correct basis for a halt status decision prevents
anyone from correctly disagreeing with this basis within this
validated basis.
If D(D) halts then H(D,D) should return a decision of halts (1).
/Flibble
On 10/20/2022 2:28 PM, Fred. Zwarts wrote:
Op 19.okt..2022 om 19:28 schreef olcott:
On 10/19/2022 12:13 PM, Fred. Zwarts wrote:
Op 19.okt..2022 om 19:01 schreef olcott:
On 10/19/2022 11:43 AM, Fred. Zwarts wrote:
Op 18.okt..2022 om 21:46 schreef olcott:
On 10/18/2022 2:23 PM, Fred. Zwarts wrote:
Op 18.okt..2022 om 17:02 schreef olcott:
On 10/18/2022 3:17 AM, Fred. Zwarts wrote:
Op 17.okt..2022 om 23:22 schreef olcott:
On 10/17/2022 1:44 PM, Fred. Zwarts wrote:
Op 17.okt..2022 om 16:29 schreef olcott:
On 10/17/2022 4:30 AM, 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.)
*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.
An alternative definition for a halt decider approved by >>>>>>>>>>>> MIT Professor Michael Sipser (author of the best selling >>>>>>>>>>>> book on the theory of computation)
https://www.amazon.com/Introduction-Theory-Computation-Sipser/dp/8131525295
is shown above and paraphrased below:
Would D correctly simulated by H ever stop running if >>>>>>>>>>>> not aborted?
Is proven on page 3 of this paper to be "no" thus
perfectly meeting the Sipser approved criteria shown >>>>>>>>>>>> above.
*Rebutting the Sipser Halting Problem Proof*
https://www.researchgate.net/publication/364302709_Rebutting_the_Sipser_Halting_Problem_Proof
It is not clear to me what you want to say and why you >>>>>>>>>>> left out my other points from the quote. You quote only >>>>>>>>>>> the definitions. You left out the points that follow from >>>>>>>>>>> the definitions. What does that mean. Don't you agree
with the definitions, or is something wrong with the
other points?
*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. >>>>>>>>>>
Because the above seems to agree with my definition of a >>>>>>>>>> simulating halt decider other definitions that do not
apply to simulating halt deciders are irrelevant.
I was not talking about simulating halt deciders, but about >>>>>>>>> halt deciders. Since we seem to agree that they are not the >>>>>>>>> same, I have to conclude that your contribution is
irrelevant.
That is the same as saying that airplanes do not fly because >>>>>>>> cars do not fly and we were talking about cars.
If we are talking about cars, it is irrelevant to change the
subject to airplanes.
But if you think your car is an airplane, it is dangerous to
try to fly with it.
*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.
Seems to be saying that a simulating halt decider does
correctly determine the halt status of its input.
The only requirement for a halt decider is that it does
correctly determine the halt status of its inputs.
I started this thread with a question about Halt Deciders. I
included a definition (see above). Why do you keep changing the
subject to things with other definitions? Cars, airplanes,
simulating halt deciders, boats, automobiles? Please, stay at
the subject.
The above quote seems to say that a simulating halt decider does
correctly determine the halt status of the input that it
simulates.
Professor Sipser is the author of the best selling book on the
theory of computation would seem to have the knowledge required
to approve alternative definitions for halt deciders.
https://www.amazon.com/Introduction-Theory-Computation-Sipser/dp/8131525295
Only the notion of a simulating halt decider defeats the
conventional HP proofs. To insist on definitions that cannot
defeat these proofs seems a little silly.
So, your contribution is irrelevant, because you want to change
definitions and you cannot show any error in the 9 points I was
asking about.
Don't change the subject, please.
In computability theory, the halting problem is the problem of
determining, from a description of an arbitrary computer program
and an input, whether the program will finish running, or continue
to run forever. Alan Turing proved in 1936 that a general
algorithm to solve the halting problem for all possible
program-input pairs cannot exist.
For any program H that might determine if programs halt, a
"pathological" program D, called with some input, can pass its own
source and its input to H and then specifically do the opposite of
what H predicts D will do. No H can exist that handles this case.
https://en.wikipedia.org/wiki/Halting_problem
H(D,D) correctly simulates its input D until H correctly
determines that its simulated D would never stop running unless
aborted thus exactly matching the Wikipedia definition of an H can
that handles this case.
Your H returns 0, but D halts. Again you changed the subject.
You continue to look for a black dog in the kitchen by looking for a
white cat in the living room because you only understand these things
on the basis of learned-by-rote.
That the behavior of the input D correctly simulated by H is
validated as the correct basis for a halt status decision prevents
anyone from correctly disagreeing with this basis within this
validated basis.
On Thu, 20 Oct 2022 16:44:31 -0500
olcott <polcott2@gmail.com> wrote:
On 10/20/2022 4:29 PM, Mr Flibble wrote:
On Thu, 20 Oct 2022 14:58:01 -0500
olcott <polcott2@gmail.com> wrote:
On 10/20/2022 2:28 PM, Fred. Zwarts wrote:
Op 19.okt..2022 om 19:28 schreef olcott:
On 10/19/2022 12:13 PM, Fred. Zwarts wrote:
Op 19.okt..2022 om 19:01 schreef olcott:
On 10/19/2022 11:43 AM, Fred. Zwarts wrote:
Op 18.okt..2022 om 21:46 schreef olcott:
On 10/18/2022 2:23 PM, Fred. Zwarts wrote:
Op 18.okt..2022 om 17:02 schreef olcott:
On 10/18/2022 3:17 AM, Fred. Zwarts wrote:If we are talking about cars, it is irrelevant to change the >>>>>>>>>>> subject to airplanes.
Op 17.okt..2022 om 23:22 schreef olcott:
On 10/17/2022 1:44 PM, Fred. Zwarts wrote:
Op 17.okt..2022 om 16:29 schreef olcott:
On 10/17/2022 4:30 AM, 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?*Professor Sipser has agreed to these verbatim words* >>>>>>>>>>>>>>>> (and no more)
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.) >>>>>>>>>>>>>>>>
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.
An alternative definition for a halt decider approved >>>>>>>>>>>>>>>> by MIT Professor Michael Sipser (author of the best >>>>>>>>>>>>>>>> selling book on the theory of computation)
https://www.amazon.com/Introduction-Theory-Computation-Sipser/dp/8131525295
is shown above and paraphrased below:
Would D correctly simulated by H ever stop running if >>>>>>>>>>>>>>>> not aborted?
Is proven on page 3 of this paper to be "no" thus >>>>>>>>>>>>>>>> perfectly meeting the Sipser approved criteria shown >>>>>>>>>>>>>>>> above.
*Rebutting the Sipser Halting Problem Proof*
https://www.researchgate.net/publication/364302709_Rebutting_the_Sipser_Halting_Problem_Proof
It is not clear to me what you want to say and why you >>>>>>>>>>>>>>> left out my other points from the quote. You quote only >>>>>>>>>>>>>>> the definitions. You left out the points that follow >>>>>>>>>>>>>>> from the definitions. What does that mean. Don't you >>>>>>>>>>>>>>> agree with the definitions, or is something wrong with >>>>>>>>>>>>>>> the other points?
*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.
Because the above seems to agree with my definition of a >>>>>>>>>>>>>> simulating halt decider other definitions that do not >>>>>>>>>>>>>> apply to simulating halt deciders are irrelevant.
I was not talking about simulating halt deciders, but >>>>>>>>>>>>> about halt deciders. Since we seem to agree that they are >>>>>>>>>>>>> not the same, I have to conclude that your contribution is >>>>>>>>>>>>> irrelevant.
That is the same as saying that airplanes do not fly
because cars do not fly and we were talking about cars. >>>>>>>>>>>
But if you think your car is an airplane, it is dangerous to >>>>>>>>>>> try to fly with it.
*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.
Seems to be saying that a simulating halt decider does
correctly determine the halt status of its input.
The only requirement for a halt decider is that it does
correctly determine the halt status of its inputs.
I started this thread with a question about Halt Deciders. I >>>>>>>>> included a definition (see above). Why do you keep changing
the subject to things with other definitions? Cars, airplanes, >>>>>>>>> simulating halt deciders, boats, automobiles? Please, stay at >>>>>>>>> the subject.
The above quote seems to say that a simulating halt decider
does correctly determine the halt status of the input that it
simulates.
Professor Sipser is the author of the best selling book on the >>>>>>>> theory of computation would seem to have the knowledge required >>>>>>>> to approve alternative definitions for halt deciders.
https://www.amazon.com/Introduction-Theory-Computation-Sipser/dp/8131525295
Only the notion of a simulating halt decider defeats the
conventional HP proofs. To insist on definitions that cannot
defeat these proofs seems a little silly.
So, your contribution is irrelevant, because you want to change
definitions and you cannot show any error in the 9 points I was
asking about.
Don't change the subject, please.
In computability theory, the halting problem is the problem of
determining, from a description of an arbitrary computer program
and an input, whether the program will finish running, or
continue to run forever. Alan Turing proved in 1936 that a
general algorithm to solve the halting problem for all possible
program-input pairs cannot exist.
For any program H that might determine if programs halt, a
"pathological" program D, called with some input, can pass its
own source and its input to H and then specifically do the
opposite of what H predicts D will do. No H can exist that
handles this case. https://en.wikipedia.org/wiki/Halting_problem
H(D,D) correctly simulates its input D until H correctly
determines that its simulated D would never stop running unless
aborted thus exactly matching the Wikipedia definition of an H
can that handles this case.
Your H returns 0, but D halts. Again you changed the subject.
You continue to look for a black dog in the kitchen by looking for
a white cat in the living room because you only understand these
things on the basis of learned-by-rote.
That the behavior of the input D correctly simulated by H is
validated as the correct basis for a halt status decision prevents
anyone from correctly disagreeing with this basis within this
validated basis.
If D(D) halts then H(D,D) should return a decision of halts (1).
/Flibble
One would think so until one looked at all of the details.
If D(D) halts then H(D,D) should return a decision of halts (1).
/Flibble
On 10/20/2022 4:29 PM, Mr Flibble wrote:
On Thu, 20 Oct 2022 14:58:01 -0500
olcott <polcott2@gmail.com> wrote:
On 10/20/2022 2:28 PM, Fred. Zwarts wrote:
Op 19.okt..2022 om 19:28 schreef olcott:
On 10/19/2022 12:13 PM, Fred. Zwarts wrote:
Op 19.okt..2022 om 19:01 schreef olcott:
On 10/19/2022 11:43 AM, Fred. Zwarts wrote:
Op 18.okt..2022 om 21:46 schreef olcott:
On 10/18/2022 2:23 PM, Fred. Zwarts wrote:
Op 18.okt..2022 om 17:02 schreef olcott:
On 10/18/2022 3:17 AM, Fred. Zwarts wrote:
Op 17.okt..2022 om 23:22 schreef olcott:
On 10/17/2022 1:44 PM, Fred. Zwarts wrote:
Op 17.okt..2022 om 16:29 schreef olcott:
On 10/17/2022 4:30 AM, 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?*Professor Sipser has agreed to these verbatim words* >>>>>>>>>>>>>> (and no more)
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.) >>>>>>>>>>>>>>
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.
An alternative definition for a halt decider approved >>>>>>>>>>>>>> by MIT Professor Michael Sipser (author of the best >>>>>>>>>>>>>> selling book on the theory of computation)
https://www.amazon.com/Introduction-Theory-Computation-Sipser/dp/8131525295
is shown above and paraphrased below:
Would D correctly simulated by H ever stop running if >>>>>>>>>>>>>> not aborted?
Is proven on page 3 of this paper to be "no" thus >>>>>>>>>>>>>> perfectly meeting the Sipser approved criteria shown >>>>>>>>>>>>>> above.
*Rebutting the Sipser Halting Problem Proof*
https://www.researchgate.net/publication/364302709_Rebutting_the_Sipser_Halting_Problem_Proof
It is not clear to me what you want to say and why you >>>>>>>>>>>>> left out my other points from the quote. You quote only >>>>>>>>>>>>> the definitions. You left out the points that follow >>>>>>>>>>>>> from the definitions. What does that mean. Don't you >>>>>>>>>>>>> agree with the definitions, or is something wrong with >>>>>>>>>>>>> the other points?
*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.
Because the above seems to agree with my definition of a >>>>>>>>>>>> simulating halt decider other definitions that do not >>>>>>>>>>>> apply to simulating halt deciders are irrelevant.
I was not talking about simulating halt deciders, but
about halt deciders. Since we seem to agree that they are >>>>>>>>>>> not the same, I have to conclude that your contribution is >>>>>>>>>>> irrelevant.
That is the same as saying that airplanes do not fly
because cars do not fly and we were talking about cars.
If we are talking about cars, it is irrelevant to change the >>>>>>>>> subject to airplanes.
But if you think your car is an airplane, it is dangerous to >>>>>>>>> try to fly with it.
*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.
Seems to be saying that a simulating halt decider does
correctly determine the halt status of its input.
The only requirement for a halt decider is that it does
correctly determine the halt status of its inputs.
I started this thread with a question about Halt Deciders. I
included a definition (see above). Why do you keep changing
the subject to things with other definitions? Cars, airplanes, >>>>>>> simulating halt deciders, boats, automobiles? Please, stay at
the subject.
The above quote seems to say that a simulating halt decider
does correctly determine the halt status of the input that it
simulates.
Professor Sipser is the author of the best selling book on the
theory of computation would seem to have the knowledge required
to approve alternative definitions for halt deciders.
https://www.amazon.com/Introduction-Theory-Computation-Sipser/dp/8131525295
Only the notion of a simulating halt decider defeats the
conventional HP proofs. To insist on definitions that cannot
defeat these proofs seems a little silly.
So, your contribution is irrelevant, because you want to change
definitions and you cannot show any error in the 9 points I was
asking about.
Don't change the subject, please.
In computability theory, the halting problem is the problem of
determining, from a description of an arbitrary computer program
and an input, whether the program will finish running, or
continue to run forever. Alan Turing proved in 1936 that a
general algorithm to solve the halting problem for all possible
program-input pairs cannot exist.
For any program H that might determine if programs halt, a
"pathological" program D, called with some input, can pass its
own source and its input to H and then specifically do the
opposite of what H predicts D will do. No H can exist that
handles this case. https://en.wikipedia.org/wiki/Halting_problem
H(D,D) correctly simulates its input D until H correctly
determines that its simulated D would never stop running unless
aborted thus exactly matching the Wikipedia definition of an H
can that handles this case.
Your H returns 0, but D halts. Again you changed the subject.
You continue to look for a black dog in the kitchen by looking for
a white cat in the living room because you only understand these
things on the basis of learned-by-rote.
That the behavior of the input D correctly simulated by H is
validated as the correct basis for a halt status decision prevents
anyone from correctly disagreeing with this basis within this
validated basis.
If D(D) halts then H(D,D) should return a decision of halts (1).
/Flibble
One would think so until one looked at all of the details.
| Sysop: | Keyop |
|---|---|
| Location: | Huddersfield, West Yorkshire, UK |
| Users: | 384 |
| Nodes: | 16 (3 / 13) |
| Uptime: | 60:10:25 |
| Calls: | 8,173 |
| Calls today: | 5 |
| Files: | 13,113 |
| Messages: | 5,864,381 |