Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]
Groups > comp.software-eng > #3583
| From | André G. Isaak <agisaak@gm.invalid> |
|---|---|
| Newsgroups | comp.theory, sci.logic, sci.math, comp.software-eng |
| Subject | Re: Did I encode Sipser correctly? (it seemed too easy) |
| Date | 2022-07-09 15:51 -0600 |
| Organization | Christians and Atheists United Against Creeping Agnosticism |
| Message-ID | <tact85$156gr$1@dont-email.me> (permalink) |
| References | (7 earlier) <FLCdndE-T7YCcFT_nZ2dnUU7_8xh4p2d@giganews.com> <tacqvi$14vrs$1@dont-email.me> <U42dnYFcnbexbFT_nZ2dnUU7_83NnZ2d@giganews.com> <tacs8d$15373$1@dont-email.me> <O_ydnRe-ob-Sa1T_nZ2dnUU7_8xh4p2d@giganews.com> |
Cross-posted to 4 groups.
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é -- To email remove 'invalid' & replace 'gm' with well known Google mail service.
Back to comp.software-eng | Previous | Next — Previous in thread | Next in thread | Find similar | Unroll thread
Re: Did I encode Sipser correctly? (it seemed too easy) olcott <NoOne@NoWhere.com> - 2022-07-09 14:26 -0500
Re: Did I encode Sipser correctly? (it seemed too easy) André G. Isaak <agisaak@gm.invalid> - 2022-07-09 13:45 -0600
Re: Did I encode Sipser correctly? (it seemed too easy) olcott <NoOne@NoWhere.com> - 2022-07-09 14:51 -0500
Re: Did I encode Sipser correctly? (it seemed too easy) André G. Isaak <agisaak@gm.invalid> - 2022-07-09 14:03 -0600
Re: Did I encode Sipser correctly? (it seemed too easy) olcott <NoOne@NoWhere.com> - 2022-07-09 15:44 -0500
Re: Did I encode Sipser correctly? (it seemed too easy) André G. Isaak <agisaak@gm.invalid> - 2022-07-09 15:03 -0600
Re: Did I encode Sipser correctly? (it seemed too easy) olcott <NoOne@NoWhere.com> - 2022-07-09 16:05 -0500
Re: Did I encode Sipser correctly? (it seemed too easy) André G. Isaak <agisaak@gm.invalid> - 2022-07-09 15:12 -0600
Re: Did I encode Sipser correctly? (it seemed too easy) olcott <NoOne@NoWhere.com> - 2022-07-09 16:20 -0500
Re: Did I encode Sipser correctly? (it seemed too easy) André G. Isaak <agisaak@gm.invalid> - 2022-07-09 15:34 -0600
Re: Did I encode Sipser correctly? (it seemed too easy) olcott <NoOne@NoWhere.com> - 2022-07-09 16:41 -0500
Re: Did I encode Sipser correctly? (it seemed too easy) André G. Isaak <agisaak@gm.invalid> - 2022-07-09 15:51 -0600
Re: Did I encode Sipser correctly? (it seemed too easy) olcott <NoOne@NoWhere.com> - 2022-07-09 17:05 -0500
Re: Did I encode Sipser correctly? (it seemed too easy) André G. Isaak <agisaak@gm.invalid> - 2022-07-09 16:24 -0600
Re: Did I encode Sipser correctly? (it seemed too easy) olcott <NoOne@NoWhere.com> - 2022-07-09 16:44 -0500
Re: Did I encode Sipser correctly? (it seemed too easy) olcott <NoOne@NoWhere.com> - 2022-07-09 16:33 -0500
Re: Did I encode Sipser correctly? (it seemed too easy) Richard Damon <Richard@Damon-Family.org> - 2022-07-09 16:11 -0400
Re: Did I encode Sipser correctly? (it seemed too easy) André G. Isaak <agisaak@gm.invalid> - 2022-07-09 14:14 -0600
Re: Did I encode Sipser correctly? (it seemed too easy) Richard Damon <Richard@Damon-Family.org> - 2022-07-09 16:26 -0400
Re: Did I encode Sipser correctly? (it seemed too easy) André G. Isaak <agisaak@gm.invalid> - 2022-07-09 15:59 -0600
Re: Did I encode Sipser correctly? (it seemed too easy) Richard Damon <Richard@Damon-Family.org> - 2022-07-09 18:37 -0400
Re: Did I encode Sipser correctly? (it seemed too easy) André G. Isaak <agisaak@gm.invalid> - 2022-07-09 16:48 -0600
Re: Did I encode Sipser correctly? (it seemed too easy) Richard Damon <Richard@Damon-Family.org> - 2022-07-09 19:11 -0400
Re: Did I encode Sipser correctly? (it seemed too easy) olcott <NoOne@NoWhere.com> - 2022-07-09 15:51 -0500
Re: Did I encode Sipser correctly? (it seemed too easy) Richard Damon <Richard@Damon-Family.org> - 2022-07-09 17:40 -0400
Re: Did I encode Sipser correctly? (it seemed too easy) [wrong source code corrected] olcott <NoOne@NoWhere.com> - 2022-07-09 15:54 -0500
Re: Did I encode Sipser correctly? (it seemed too easy) olcott <NoOne@NoWhere.com> - 2022-07-09 14:57 -0500
csiph-web