On 2022-07-09 13:26, olcott wrote:
On 7/9/2022 1:08 PM, olcott wrote:
https://www.liarparadox.org/Sipser_165_167.pdf
typedef void (*ptr)();
// Sipser's diagonal argument
int D(ptr x)
{
if (H(x,x) == 0) // reject
return 1;
else // accept
return 0;
}
int main()
{
Output("D(D) = ", D(D));
}
Why is your main() calling D(D) rather than H(D, D)? No one cares what
D(D) reports. At issue is whether H() can correctly report on the
halting status of D(D).
On 7/9/2022 1:08 PM, olcott wrote:
https://www.liarparadox.org/Sipser_165_167.pdf
typedef void (*ptr)();
// Sipser's diagonal argument
int D(ptr x)
{
if (H(x,x) == 0) // reject
return 1;
else // accept
return 0;
}
int main()
{
Output("D(D) = ", D(D));
}
If the above encoding of Sipser is correct then all that D does is incorrectly report what H(D,D) correctly reports.
This causes the diagonal argument of the halting theorem to be trivially incorrect.
On 7/9/2022 2:45 PM, André G. Isaak wrote:
On 2022-07-09 13:26, olcott wrote:
On 7/9/2022 1:08 PM, olcott wrote:
https://www.liarparadox.org/Sipser_165_167.pdf
typedef void (*ptr)();
// Sipser's diagonal argument
int D(ptr x)
{
if (H(x,x) == 0) // reject
return 1;
else // accept
return 0;
}
int main()
{
Output("D(D) = ", D(D));
}
Why is your main() calling D(D) rather than H(D, D)? No one cares what
D(D) reports. At issue is whether H() can correctly report on the
halting status of D(D).
Page 165 of Sipser indicates that D(D) derives the contradiction.
Page 165 of Sisper also indicates that D calls its subroutine H.
The best that I can tell my code exactly matches its spec on page 165.
D merely contradicts the correct answer provided by H.
If the above encoding of Sipser is correct then all that D does is
incorrectly report what H(D,D) correctly reports.
This causes the diagonal argument of the halting theorem to be
trivially incorrect.
Only because you do not understand it.
André
On 2022-07-09 13:26, olcott wrote:
On 7/9/2022 1:08 PM, olcott wrote:
https://www.liarparadox.org/Sipser_165_167.pdf
typedef void (*ptr)();
// Sipser's diagonal argument
int D(ptr x)
{
if (H(x,x) == 0) // reject
return 1;
else // accept
return 0;
}
int main()
{
Output("D(D) = ", D(D));
}
Why is your main() calling D(D) rather than H(D, D)? No one cares what
D(D) reports. At issue is whether H() can correctly report on the
halting status of D(D).
If the above encoding of Sipser is correct then all that D does is
incorrectly report what H(D,D) correctly reports.
This causes the diagonal argument of the halting theorem to be
trivially incorrect.
Only because you do not understand it.
André
https://www.liarparadox.org/Sipser_165_167.pdf
typedef void (*ptr)();
// Sipser's diagonal argument
int D(ptr x)
{
if (H(x,x) == 0) // reject
return 1;
else // accept
return 0;
}
int main()
{
Output("D(D) = ", D(D));
}
On 7/9/2022 2:45 PM, André G. Isaak wrote:
On 2022-07-09 13:26, olcott wrote:
On 7/9/2022 1:08 PM, olcott wrote:
https://www.liarparadox.org/Sipser_165_167.pdf
typedef void (*ptr)();
// Sipser's diagonal argument
int D(ptr x)
{
if (H(x,x) == 0) // reject
return 1;
else // accept
return 0;
}
int main()
{
Output("D(D) = ", D(D));
}
Why is your main() calling D(D) rather than H(D, D)? No one cares what
D(D) reports. At issue is whether H() can correctly report on the
halting status of D(D).
Page 165 of Sipser indicates that D(D) derives the contradiction.
Page 165 of Sisper also indicates that D calls its subroutine H.
The best that I can tell my code exactly matches its spec on page 165.
D merely contradicts the correct answer provided by H.
H is REQUIRED (to be correct) to give the answer that D will give if D
will give an answer,
and 0 if D will NEVER give an answer (as
recognizers are allowed to be non-halting for inputs they do not accept).
On 2022-07-09 14:11, Richard Damon wrote:
H is REQUIRED (to be correct) to give the answer that D will give if D
will give an answer,
No, H is required to answer "true" if D will give an answer, regardless
of what that answer might be.
André
and 0 if D will NEVER give an answer (as recognizers are allowed to be
non-halting for inputs they do not accept).
On 2022-07-09 14:11, Richard Damon wrote:
H is REQUIRED (to be correct) to give the answer that D will give if D
will give an answer,
No, H is required to answer "true" if D will give an answer, regardless
of what that answer might be.
André
and 0 if D will NEVER give an answer (as recognizers are allowed to be
non-halting for inputs they do not accept).
On 2022-07-09 13:51, olcott wrote:
On 7/9/2022 2:45 PM, André G. Isaak wrote:
On 2022-07-09 13:26, olcott wrote:
On 7/9/2022 1:08 PM, olcott wrote:
https://www.liarparadox.org/Sipser_165_167.pdf
typedef void (*ptr)();
// Sipser's diagonal argument
int D(ptr x)
{
if (H(x,x) == 0) // reject
return 1;
else // accept
return 0;
}
int main()
{
Output("D(D) = ", D(D));
}
Why is your main() calling D(D) rather than H(D, D)? No one cares
what D(D) reports. At issue is whether H() can correctly report on
the halting status of D(D).
Page 165 of Sipser indicates that D(D) derives the contradiction.
Page 165 of Sisper also indicates that D calls its subroutine H.
The best that I can tell my code exactly matches its spec on page 165.
D merely contradicts the correct answer provided by H.
You're completely misreading sipser. The sipser proof is *identical* to
the Linz proof. He does not say that D *returns* the opposite value that
H does but rather that it *does* the opposite of what H claims it will
do. i.e. it halts if H claims it doesn't and it doesn't halt if H claims
it does. D(D) derives a contradiction when passed as an input to H().
All you've done above is flipped the return values.
André
On 2022-07-09 14:44, olcott wrote:
On 7/9/2022 3:03 PM, André G. Isaak wrote:
On 2022-07-09 13:51, olcott wrote:
On 7/9/2022 2:45 PM, André G. Isaak wrote:
On 2022-07-09 13:26, olcott wrote:
On 7/9/2022 1:08 PM, olcott wrote:
https://www.liarparadox.org/Sipser_165_167.pdf
typedef void (*ptr)();
// Sipser's diagonal argument
int D(ptr x)
{
if (H(x,x) == 0) // reject
return 1;
else // accept
return 0;
}
int main()
{
Output("D(D) = ", D(D));
}
Why is your main() calling D(D) rather than H(D, D)? No one cares
what D(D) reports. At issue is whether H() can correctly report on
the halting status of D(D).
Page 165 of Sipser indicates that D(D) derives the contradiction.
Page 165 of Sisper also indicates that D calls its subroutine H.
The best that I can tell my code exactly matches its spec on page 165. >>>> D merely contradicts the correct answer provided by H.
You're completely misreading sipser. The sipser proof is *identical*
to the Linz proof. He does not say that D *returns* the opposite
value that H does but rather that it *does* the opposite of what H
claims it will do. i.e. it halts if H claims it doesn't and it
doesn't halt if H claims it does. D(D) derives a contradiction when
passed as an input to H().
All you've done above is flipped the return values.
André
Now we construct a new Turing machine D with H as a subroutine. This
new TM calls H to determine what M does when the input to M is its own
description ⟨M⟩. Once D has determined this information, it does the
opposite. That is, it rejects if M accepts and accepts if M does not
accept. The following is a description of D.
D = "On input ⟨M⟩, where M is a TM:
1. Run H on input ⟨M, ⟨M⟩⟩.
2. Output the opposite of what H outputs; that is if H accepts
reject and if H rejects, accept."
Because you missed this in the original text I will repeat it:
Output the opposite of what H outputs;
Output the opposite of what H outputs;
Output the opposite of what H outputs;
OK. You're dealing with a different proof than the one I thought. My bad
for not reading the .pdf which you linked to.
You said you were talking about the "diagonal argument of the halting theorem", so I assumed you were talking about Sipser's proof of the
halting theorem. The diagonalization argument you are discussing here
doesn't deal directly with the halting problem (though it is closely
related to it). That proof demonstrates that not all languages are
decidable.
André
On 7/9/2022 4:03 PM, André G. Isaak wrote:
You said you were talking about the "diagonal argument of the halting
theorem", so I assumed you were talking about Sipser's proof of the
halting theorem. The diagonalization argument you are discussing here
doesn't deal directly with the halting problem (though it is closely
related to it). That proof demonstrates that not all languages are
decidable.
André
So you also never noticed the title of the post?
Did I encode Sipser correctly?
On 7/9/2022 3:03 PM, André G. Isaak wrote:
On 2022-07-09 13:51, olcott wrote:
On 7/9/2022 2:45 PM, André G. Isaak wrote:
On 2022-07-09 13:26, olcott wrote:
On 7/9/2022 1:08 PM, olcott wrote:
https://www.liarparadox.org/Sipser_165_167.pdf
typedef void (*ptr)();
// Sipser's diagonal argument
int D(ptr x)
{
if (H(x,x) == 0) // reject
return 1;
else // accept
return 0;
}
int main()
{
Output("D(D) = ", D(D));
}
Why is your main() calling D(D) rather than H(D, D)? No one cares
what D(D) reports. At issue is whether H() can correctly report on
the halting status of D(D).
Page 165 of Sipser indicates that D(D) derives the contradiction.
Page 165 of Sisper also indicates that D calls its subroutine H.
The best that I can tell my code exactly matches its spec on page 165.
D merely contradicts the correct answer provided by H.
You're completely misreading sipser. The sipser proof is *identical*
to the Linz proof. He does not say that D *returns* the opposite value
that H does but rather that it *does* the opposite of what H claims it
will do. i.e. it halts if H claims it doesn't and it doesn't halt if H
claims it does. D(D) derives a contradiction when passed as an input
to H().
All you've done above is flipped the return values.
André
Now we construct a new Turing machine D with H as a subroutine. This new
TM calls H to determine what M does when the input to M is its own description ⟨M⟩. Once D has determined this information, it does the opposite. That is, it rejects if M accepts and accepts if M does not
accept. The following is a description of D.
D = "On input ⟨M⟩, where M is a TM:
1. Run H on input ⟨M, ⟨M⟩⟩.
2. Output the opposite of what H outputs; that is if H accepts
reject and if H rejects, accept."
Because you missed this in the original text I will repeat it:
Output the opposite of what H outputs;
Output the opposite of what H outputs;
Output the opposite of what H outputs;
On 2022-07-09 15:05, olcott wrote:
On 7/9/2022 4:03 PM, André G. Isaak wrote:
You said you were talking about the "diagonal argument of the halting
theorem", so I assumed you were talking about Sipser's proof of the
halting theorem. The diagonalization argument you are discussing here
doesn't deal directly with the halting problem (though it is closely
related to it). That proof demonstrates that not all languages are
decidable.
André
So you also never noticed the title of the post?
Did I encode Sipser correctly?
"Sipser" is the name of an individual and/or book, not of a proof.
Sipser gives many proofs.
It was perfectly reasonably of me to assume
you meant 'Sipser's proof of
the halting theorem' given your obsession with halt deciders and the
fact that you referred to it as the "diagonal argument of the halting theorem". (Sipser doesn't refers to it as such since that is an
inaccurate description).
André
On 2022-07-09 15:05, olcott wrote:
On 7/9/2022 4:03 PM, André G. Isaak wrote:
You said you were talking about the "diagonal argument of the halting
theorem", so I assumed you were talking about Sipser's proof of the
halting theorem. The diagonalization argument you are discussing here
doesn't deal directly with the halting problem (though it is closely
related to it). That proof demonstrates that not all languages are
decidable.
André
So you also never noticed the title of the post?
Did I encode Sipser correctly?
"Sipser" is the name of an individual and/or book, not of a proof.
Sipser gives many proofs.
It was perfectly reasonably of me to assume you meant 'Sipser's proof of
the halting theorem' given your obsession with halt deciders and the
fact that you referred to it as the "diagonal argument of the halting theorem". (Sipser doesn't refers to it as such since that is an
inaccurate description).
André
On 2022-07-09 15:20, olcott wrote:
On 7/9/2022 4:12 PM, André G. Isaak wrote:
On 2022-07-09 15:05, olcott wrote:
On 7/9/2022 4:03 PM, André G. Isaak wrote:
You said you were talking about the "diagonal argument of the
halting theorem", so I assumed you were talking about Sipser's
proof of the halting theorem. The diagonalization argument you are
discussing here doesn't deal directly with the halting problem
(though it is closely related to it). That proof demonstrates that
not all languages are decidable.
André
So you also never noticed the title of the post?
Did I encode Sipser correctly?
"Sipser" is the name of an individual and/or book, not of a proof.
Sipser gives many proofs.
And I provided the whole proof that I was referring to.
It was perfectly reasonably of me to assume
It is always totally unreasonable to ever assume anything contrary to
what was explicitly specified.
I need to carefully analyze the diagonal argument and when I did this
with Kaz it was obvious that it is not the same as Linz.
L15: Proof by Diagonalization that ATM (Halting Problem) is Not Decidable
https://www.youtube.com/watch?v=jM6osxSX9GA
ATM as described in both the textbook and the above video is *not* the halting problem.
André
On 7/9/2022 3:14 PM, André G. Isaak wrote:
On 2022-07-09 14:11, Richard Damon wrote:
H is REQUIRED (to be correct) to give the answer that D will give if
D will give an answer,
No, H is required to answer "true" if D will give an answer,
regardless of what that answer might be.
typedef void (*ptr)();
// Sipser's diagonal argument
int D(ptr x)
{
if (H(x,x) == 0) // reject
return 1;
else // accept
return 0;
}
int main()
{
Output("D(D) = ", D(D));
}
Ah that proves my H is correct. D is stuck in infinitely recursive
emulation unable to provide any answer.
André
and 0 if D will NEVER give an answer (as recognizers are allowed to
be non-halting for inputs they do not accept).
On 7/9/2022 4:12 PM, André G. Isaak wrote:
On 2022-07-09 15:05, olcott wrote:
On 7/9/2022 4:03 PM, André G. Isaak wrote:
You said you were talking about the "diagonal argument of the
halting theorem", so I assumed you were talking about Sipser's proof
of the halting theorem. The diagonalization argument you are
discussing here doesn't deal directly with the halting problem
(though it is closely related to it). That proof demonstrates that
not all languages are decidable.
André
So you also never noticed the title of the post?
Did I encode Sipser correctly?
"Sipser" is the name of an individual and/or book, not of a proof.
Sipser gives many proofs.
And I provided the whole proof that I was referring to.
It was perfectly reasonably of me to assume
It is always totally unreasonable to ever assume anything contrary to
what was explicitly specified.
I need to carefully analyze the diagonal argument and when I did this
with Kaz it was obvious that it is not the same as Linz.
L15: Proof by Diagonalization that ATM (Halting Problem) is Not Decidable https://www.youtube.com/watch?v=jM6osxSX9GA
On 2022-07-09 15:20, olcott wrote:
On 7/9/2022 4:12 PM, André G. Isaak wrote:
On 2022-07-09 15:05, olcott wrote:
On 7/9/2022 4:03 PM, André G. Isaak wrote:
You said you were talking about the "diagonal argument of the
halting theorem", so I assumed you were talking about Sipser's
proof of the halting theorem. The diagonalization argument you are
discussing here doesn't deal directly with the halting problem
(though it is closely related to it). That proof demonstrates that
not all languages are decidable.
André
So you also never noticed the title of the post?
Did I encode Sipser correctly?
"Sipser" is the name of an individual and/or book, not of a proof.
Sipser gives many proofs.
And I provided the whole proof that I was referring to.
It was perfectly reasonably of me to assume
It is always totally unreasonable to ever assume anything contrary to
what was explicitly specified.
I need to carefully analyze the diagonal argument and when I did this
with Kaz it was obvious that it is not the same as Linz.
L15: Proof by Diagonalization that ATM (Halting Problem) is Not Decidable
https://www.youtube.com/watch?v=jM6osxSX9GA
ATM as described in both the textbook and the above video is *not* the halting problem.
André
On 7/9/22 4:14 PM, André G. Isaak wrote:
On 2022-07-09 14:11, Richard Damon wrote:
H is REQUIRED (to be correct) to give the answer that D will give if
D will give an answer,
No, H is required to answer "true" if D will give an answer,
regardless of what that answer might be.
I though in Sipser, H was supposed to be a decider where H accepts D,x
if D will accept x, and reject if D doesn't accept x (either reject or not-answer).
D is then defined to accept if T rejects and rejects if T accepts.
On 2022-07-09 15:41, olcott wrote:
On 7/9/2022 4:34 PM, André G. Isaak wrote:
On 2022-07-09 15:20, olcott wrote:
On 7/9/2022 4:12 PM, André G. Isaak wrote:
On 2022-07-09 15:05, olcott wrote:
On 7/9/2022 4:03 PM, André G. Isaak wrote:
You said you were talking about the "diagonal argument of the
halting theorem", so I assumed you were talking about Sipser's
proof of the halting theorem. The diagonalization argument you
are discussing here doesn't deal directly with the halting
problem (though it is closely related to it). That proof
demonstrates that not all languages are decidable.
André
So you also never noticed the title of the post?
Did I encode Sipser correctly?
"Sipser" is the name of an individual and/or book, not of a proof.
Sipser gives many proofs.
And I provided the whole proof that I was referring to.
It was perfectly reasonably of me to assume
It is always totally unreasonable to ever assume anything contrary
to what was explicitly specified.
I need to carefully analyze the diagonal argument and when I did
this with Kaz it was obvious that it is not the same as Linz.
L15: Proof by Diagonalization that ATM (Halting Problem) is Not
Decidable
https://www.youtube.com/watch?v=jM6osxSX9GA
ATM as described in both the textbook and the above video is *not*
the halting problem.
André
What do you mean by this?
ATM is a language consisting of all strings <M, w> such that M *accepts*
w. His diagonalization proof shows that ATM is not a decidable language.
It follows as a straightforward corollary that halting is undecidable,
but whether ATM is decidable and whether halting is decidable are two separate (though related) problems.
André
On 7/9/2022 4:34 PM, André G. Isaak wrote:
On 2022-07-09 15:20, olcott wrote:
On 7/9/2022 4:12 PM, André G. Isaak wrote:
On 2022-07-09 15:05, olcott wrote:
On 7/9/2022 4:03 PM, André G. Isaak wrote:
You said you were talking about the "diagonal argument of the
halting theorem", so I assumed you were talking about Sipser's
proof of the halting theorem. The diagonalization argument you are >>>>>> discussing here doesn't deal directly with the halting problem
(though it is closely related to it). That proof demonstrates that >>>>>> not all languages are decidable.
André
So you also never noticed the title of the post?
Did I encode Sipser correctly?
"Sipser" is the name of an individual and/or book, not of a proof.
Sipser gives many proofs.
And I provided the whole proof that I was referring to.
It was perfectly reasonably of me to assume
It is always totally unreasonable to ever assume anything contrary to
what was explicitly specified.
I need to carefully analyze the diagonal argument and when I did this
with Kaz it was obvious that it is not the same as Linz.
L15: Proof by Diagonalization that ATM (Halting Problem) is Not
Decidable
https://www.youtube.com/watch?v=jM6osxSX9GA
ATM as described in both the textbook and the above video is *not* the
halting problem.
André
What do you mean by this?
On 2022-07-09 14:26, Richard Damon wrote:
On 7/9/22 4:14 PM, André G. Isaak wrote:
On 2022-07-09 14:11, Richard Damon wrote:
H is REQUIRED (to be correct) to give the answer that D will give if
D will give an answer,
No, H is required to answer "true" if D will give an answer,
regardless of what that answer might be.
I though in Sipser, H was supposed to be a decider where H accepts D,x
if D will accept x, and reject if D doesn't accept x (either reject or
not-answer).
D is then defined to accept if T rejects and rejects if T accepts.
mea culpa. I was confused by Sipser's use of H to refer not to a halt
decider but to a decider of A_TM. Admittedly I should have verified this against the PDF.
André
On 7/9/22 5:59 PM, André G. Isaak wrote:
On 2022-07-09 14:26, Richard Damon wrote:
On 7/9/22 4:14 PM, André G. Isaak wrote:
On 2022-07-09 14:11, Richard Damon wrote:
H is REQUIRED (to be correct) to give the answer that D will give
if D will give an answer,
No, H is required to answer "true" if D will give an answer,
regardless of what that answer might be.
I though in Sipser, H was supposed to be a decider where H accepts
D,x if D will accept x, and reject if D doesn't accept x (either
reject or not-answer).
D is then defined to accept if T rejects and rejects if T accepts.
mea culpa. I was confused by Sipser's use of H to refer not to a halt
decider but to a decider of A_TM. Admittedly I should have verified
this against the PDF.
André
Yes, the notation adopted in that paper is a bit confusing.
Not certain which book he his violating the Copyrights of, but it seems poorly edited.
It looks like he has created a dummy Word Press sight just to post these copyright violations on.
I can't see how without attached comments (just highlighting) it comes
close to the requirements of "Fair Use"
On 7/9/2022 4:51 PM, André G. Isaak wrote:
On 2022-07-09 15:41, olcott wrote:
On 7/9/2022 4:34 PM, André G. Isaak wrote:
On 2022-07-09 15:20, olcott wrote:
On 7/9/2022 4:12 PM, André G. Isaak wrote:
On 2022-07-09 15:05, olcott wrote:
On 7/9/2022 4:03 PM, André G. Isaak wrote:
You said you were talking about the "diagonal argument of the
halting theorem", so I assumed you were talking about Sipser's >>>>>>>> proof of the halting theorem. The diagonalization argument you >>>>>>>> are discussing here doesn't deal directly with the halting
problem (though it is closely related to it). That proof
demonstrates that not all languages are decidable.
André
So you also never noticed the title of the post?
Did I encode Sipser correctly?
"Sipser" is the name of an individual and/or book, not of a proof. >>>>>> Sipser gives many proofs.
And I provided the whole proof that I was referring to.
It was perfectly reasonably of me to assume
It is always totally unreasonable to ever assume anything contrary
to what was explicitly specified.
I need to carefully analyze the diagonal argument and when I did
this with Kaz it was obvious that it is not the same as Linz.
L15: Proof by Diagonalization that ATM (Halting Problem) is Not
Decidable
https://www.youtube.com/watch?v=jM6osxSX9GA
ATM as described in both the textbook and the above video is *not*
the halting problem.
André
What do you mean by this?
ATM is a language consisting of all strings <M, w> such that M
*accepts* w. His diagonalization proof shows that ATM is not a
decidable language. It follows as a straightforward corollary that
halting is undecidable, but whether ATM is decidable and whether
halting is decidable are two separate (though related) problems.
André
I still need to know whether or not I encoded Sipser correctly:
typedef void (*ptr)();
// Sipser's diagonal argument
int D(ptr x)
{
if (H(x,x) == 0) // reject
return 1;
else // accept
return 0;
}
int main()
{
Output("Input_Halts = ", H(D, D));
}
On 2022-07-09 16:37, Richard Damon wrote:
On 7/9/22 5:59 PM, André G. Isaak wrote:
On 2022-07-09 14:26, Richard Damon wrote:
On 7/9/22 4:14 PM, André G. Isaak wrote:
On 2022-07-09 14:11, Richard Damon wrote:
H is REQUIRED (to be correct) to give the answer that D will give
if D will give an answer,
No, H is required to answer "true" if D will give an answer,
regardless of what that answer might be.
I though in Sipser, H was supposed to be a decider where H accepts
D,x if D will accept x, and reject if D doesn't accept x (either
reject or not-answer).
D is then defined to accept if T rejects and rejects if T accepts.
mea culpa. I was confused by Sipser's use of H to refer not to a halt
decider but to a decider of A_TM. Admittedly I should have verified
this against the PDF.
André
Yes, the notation adopted in that paper is a bit confusing.
Not certain which book he his violating the Copyrights of, but it
seems poorly edited.
It looks like he has created a dummy Word Press sight just to post
these copyright violations on.
I can't see how without attached comments (just highlighting) it comes
close to the requirements of "Fair Use"
It is a bit strange that someone who insists on putting a copyright
notice on even the most asinine things has such little regard for
copyright.
André
| Sysop: | Keyop |
|---|---|
| Location: | Huddersfield, West Yorkshire, UK |
| Users: | 299 |
| Nodes: | 16 (2 / 14) |
| Uptime: | 66:21:27 |
| Calls: | 6,691 |
| Calls today: | 1 |
| Files: | 12,228 |
| Messages: | 5,345,979 |
| Posted today: | 1 |