On Mon, 17 Oct 2022 11:42:22 -0500
olcott <polcott2@gmail.com> wrote:
On 10/17/2022 11:33 AM, Dennis Bush wrote:
On Monday, October 17, 2022 at 12:29:34 PM UTC-4, olcott wrote:
On 10/17/2022 11:25 AM, Dennis Bush wrote:
On Monday, October 17, 2022 at 12:15:27 PM UTC-4, olcott wrote:The halting problem proofs make claims about the halting function
On 10/17/2022 11:00 AM, Dennis Bush wrote:
On Monday, October 17, 2022 at 11:57:18 AM UTC-4, olcott wrote:
On 10/17/2022 10:47 AM, Dennis Bush wrote:
On Monday, October 17, 2022 at 11:44:10 AM UTC-4, olcottAnyone that is sufficiently technically competent can verify
wrote:
On 10/17/2022 10:40 AM, Dennis Bush wrote:
On Monday, October 17, 2022 at 11:31:41 AM UTC-4, olcott >>>>>>>>>>> wrote:
On 10/17/2022 10:16 AM, Dennis Bush wrote:
On Monday, October 17, 2022 at 11:06:45 AM UTC-4, olcott >>>>>>>>>>>>> wrote:*The PO-halting function is now Sipser approved*
On 10/17/2022 9:49 AM, Dennis Bush wrote:
On Monday, October 17, 2022 at 10:38:09 AM UTC-4, >>>>>>>>>>>>>>> olcott wrote:I have proven an exception to this rule:
On 10/17/2022 7:47 AM, Dennis Bush wrote:
On Monday, October 17, 2022 at 5:30:59 AM UTC-4, >>>>>>>>>>>>>>>>> Fred. Zwarts wrote:*Professor Sipser has agreed to these verbatim words* >>>>>>>>>>>>>>>> (and no more) If simulating halt decider H correctly >>>>>>>>>>>>>>>> simulates its input D until H correctly determines >>>>>>>>>>>>>>>> that its simulated D would never stop running unless >>>>>>>>>>>>>>>> aborted then H can abort its simulation of D and >>>>>>>>>>>>>>>> correctly report that D specifies a non-halting >>>>>>>>>>>>>>>> sequence of configurations.
I have been following the discussions about Halt >>>>>>>>>>>>>>>>>> deciders with interest. As a retired software >>>>>>>>>>>>>>>>>> designer and developer, I have a lot of practical >>>>>>>>>>>>>>>>>> experience, but not much theoretical education, >>>>>>>>>>>>>>>>>> although the theoretical background is very >>>>>>>>>>>>>>>>>> interesting. I learned a lot. I would like to verify >>>>>>>>>>>>>>>>>> that I understand it correctly. Could you point out >>>>>>>>>>>>>>>>>> any errors in the summary below?
1) (Definition of halt) A program X with input Y is >>>>>>>>>>>>>>>>>> said to halt if it reaches its end condition after a >>>>>>>>>>>>>>>>>> finite number of steps. It does not halt if it >>>>>>>>>>>>>>>>>> continues to execute infinitely. (So, X(Y) either >>>>>>>>>>>>>>>>>> halts, or it does not halt.) (It is irrelevant >>>>>>>>>>>>>>>>>> whether the end condition is reached in the 'normal' >>>>>>>>>>>>>>>>>> way, or by other means, e.g. an unhandled
'exception'.)
2) (Definition of halt decider) A halt decider H is >>>>>>>>>>>>>>>>>> a program that, given a program X with input Y >>>>>>>>>>>>>>>>>> decides, after a finite number of steps, whether >>>>>>>>>>>>>>>>>> X(Y) halts or not. (H(X,Y) itself must halt after a >>>>>>>>>>>>>>>>>> finite number of steps. It must return either 1 if >>>>>>>>>>>>>>>>>> X(Y) halts, or 0 if X(Y) does not halt, where 1 and >>>>>>>>>>>>>>>>>> 0 are a convention, which could also be two other >>>>>>>>>>>>>>>>>> arbitrary values.)
From 1 and 2 it follows:
3) If X(Y) halts, then H must return 1. If H does >>>>>>>>>>>>>>>>>> not return 1 in a finite number of steps, it might >>>>>>>>>>>>>>>>>> return another interesting result, but it is not a >>>>>>>>>>>>>>>>>> halt decider. (Not returning 1 includes returning >>>>>>>>>>>>>>>>>> other values, not halting, or throwing 'exceptions'.) >>>>>>>>>>>>>>>>>>
4) If X(Y) does not halt, then H must return 0. If >>>>>>>>>>>>>>>>>> it does not return 0 in a finite number of steps, it >>>>>>>>>>>>>>>>>> might return another interesting result, but it is >>>>>>>>>>>>>>>>>> not a halt decider. (Not returning 0 includes >>>>>>>>>>>>>>>>>> returning other values, not halting, or throwing >>>>>>>>>>>>>>>>>> 'exceptions'.)
Paradoxical program:
5) It is always possible to construct a program P, >>>>>>>>>>>>>>>>>> that uses code with the same logic as H, in order to >>>>>>>>>>>>>>>>>> do the opposite of what H(P,P) returns. (P does not >>>>>>>>>>>>>>>>>> necessarily need to use the exact same code as H >>>>>>>>>>>>>>>>>> does, amongst others it could use a modified copy of >>>>>>>>>>>>>>>>>> H, or a simulation of H.)
From 5 it follows that a general halt decider that >>>>>>>>>>>>>>>>>> works for any X and Y does not exist:
From 3, 4 and 5 it follows:
6) If P(P) halts, then H should return 1, but if H >>>>>>>>>>>>>>>>>> would do so, P(P) would not halt.
7) If P(P) does not halt, H should return 0, but if >>>>>>>>>>>>>>>>>> H would do so, P(P) would halt.
8) If P(P) halts and H does not return 1 after a >>>>>>>>>>>>>>>>>> finite number of steps, then H is not a halt decider. >>>>>>>>>>>>>>>>>> (The result could nevertheless be interesting for >>>>>>>>>>>>>>>>>> other purposes.) (It is irrelevant what causes P(P) >>>>>>>>>>>>>>>>>> to halt.)
9) If P(P) does not halt and H does not return 0 >>>>>>>>>>>>>>>>>> after a finite number of steps, then H is not a halt >>>>>>>>>>>>>>>>>> decider. (The result could nevertheless be >>>>>>>>>>>>>>>>>> interesting for other purposes.)
Your understanding is correct. To sum things up, the >>>>>>>>>>>>>>>>> halting function (using the mathematical notion of a >>>>>>>>>>>>>>>>> function), performs the following mapping:
For *any* algorithm (i.e. a fixed immutable sequence >>>>>>>>>>>>>>>>> of instructions) X and input Y: H(X,Y)==1 if and only >>>>>>>>>>>>>>>>> if X(Y) halts, and H(X,Y)==0 if and only if X(Y) does >>>>>>>>>>>>>>>>> not halt
And the halting problem proofs show that this mapping >>>>>>>>>>>>>>>>> is not computable, i.e. it is impossible for an >>>>>>>>>>>>>>>>> algorithm to compute this mapping.
And he agreed to those words based on their commonly >>>>>>>>>>>>>>> known meanings, not your alternate weasel-word meanings. >>>>>>>>>>>>>>>
The conventional definition of "correctly simulating" >>>>>>>>>>>>>>> means that the simulated behavior EXACTLY matches the >>>>>>>>>>>>>>> behavior of direct execution.
That's not a rule. It's a definition.
int Sipser_D(int (*M)())
{
if ( Sipser_H(M, M) )
return 0;
return 1;
}
For the infinite set of H/D pairs:
Every correct simulation of D by H will never reach the >>>>>>>>>>>>>> final state of D because D specifies recursive
simulation to H.
So in other words your Sipser_H is computing the
PO-halting function:
No it's not, because he used the actual meaning of the
words and not your weasel-worded definitions. Using the
real definitions,
*Professor Sipser has agreed to these verbatim words* (and >>>>>>>>>> no more) If simulating halt decider H correctly simulates
its input D until H correctly determines that its simulated >>>>>>>>>> D would never stop running unless aborted then H can abort >>>>>>>>>> its simulation of D and correctly report that D specifies a >>>>>>>>>> non-halting sequence of configurations. *A paraphrase of a >>>>>>>>>> portion of the above paragraph* Would D correctly simulated >>>>>>>>>> by H ever stop running if not aborted?
The answer of "no" is proved on page 3 of this paper.
*Rebutting the Sipser Halting Problem Proof*
https://www.researchgate.net/publication/364302709_Rebutting_the_Sipser_Halting_Problem_Proof
*Still no rebuttal of page 3 because you know that page 3 is >>>>>>>>>> correct*
You still seem to think that because you have an H that
partially computes the PO-halting function that it has
anything to do with the halting function. It does not.
So anything that does not address whether the halting
function is computable is irrelevant.
that H does correctly determine the halt status of D correctly >>>>>>>> simulated by H.
No one is denying that you're able to compute a subset of the
PO-halting function. The halting problem proofs are about the
halting function.
This proves that the conventional proofs that rely on D doing
the opposite of whatever H decides have been refuted by the
notion of a simulating halt decider.
The conventional proofs are making claims about the halting
function, not the PO-halting function, therefore claims about
the PO-halting function are irrelevant.
[ repeat of previously refuted statement ]
int Sipser_D(int (*M)())
{
if ( Sipser_H(M, M) )
return 0;
return 1;
}
This notion of a simulating halt decider is proven to correctly
determine the halt status of Sipser_D by Sipser_H.
*Rebutting the Sipser Halting Problem Proof*
https://www.researchgate.net/publication/364302709_Rebutting_the_Sipser_Halting_Problem_Proof
In other words, you can compute a subset of the PO-halting
function. And since the halting problem proofs make claims about
the halting function, claims about the PO-halting function are
irrelevant.
on the basis that the halt status of Sipser_D cannot be correctly
determined by Sipser_H.
Correct: the halting function maps D to halting but Sipser_H maps D
to non-halting, so it is unable to compute the halting function.
*Professor Sipser has agreed to these verbatim words* (and no more)
If simulating halt decider H correctly simulates its input D until H
correctly determines that its simulated D would never stop running
unless aborted then H can abort its simulation of D and correctly
report that D specifies a non-halting sequence of configurations.
Thus professor Sipser has agreed that the above H does compute the
halting function for the above D.
Professor Sipser has specifically approved the abstract to this paper:
*Rebutting the Sipser Halting Problem Proof*
https://www.researchgate.net/publication/364302709_Rebutting_the_Sipser_Halting_Problem_Proof
If H is a Flibble Signaling Decider then H will correctly simulate its
input D however if H is an Olcott Simulation Detector H will not
correctly simulate its input D as the only correct simulation of D is
for the simulation to behave as if D(D) was directly executed.
/Flibble
...D(D) would not halt unless H stops the simulation.
H /can/ correctly determine this silly criterion
(in this one case)...
Sysop: | Keyop |
---|---|
Location: | Huddersfield, West Yorkshire, UK |
Users: | 366 |
Nodes: | 16 (2 / 14) |
Uptime: | 02:07:02 |
Calls: | 7,812 |
Calls today: | 15 |
Files: | 12,924 |
Messages: | 5,749,450 |