Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]
| 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:03 -0600 |
| Organization | Christians and Atheists United Against Creeping Agnosticism |
| Message-ID | <tacqei$14ttq$1@dont-email.me> (permalink) |
| References | (1 earlier) <8t6dnRve_qHRS1T_nZ2dnUU7_83NnZ2d@giganews.com> <taclsq$14ggb$1@dont-email.me> <ztqdna9DoMbFQVT_nZ2dnUU7_8zNnZ2d@giganews.com> <tacmvd$14jr5$1@dont-email.me> <pomdnedR5ulWdVT_nZ2dnUU7_8zNnZ2d@giganews.com> |
Cross-posted to 4 groups.
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é
--
To email remove 'invalid' & replace 'gm' with well known Google mail
service.
Back to comp.theory | Previous | Next — Previous in thread | Next in thread | Find similar | Unroll thread
Did I encode Sipser correctly? (it seemed too easy) olcott <NoOne@NoWhere.com> - 2022-07-09 13:08 -0500
Re: Did I encode Sipser correctly? (it seemed too easy) Richard Damon <Richard@Damon-Family.org> - 2022-07-09 14:41 -0400
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) Mike Terry <news.dead.person.stones@darjeeling.plus.com> - 2022-07-09 22:50 +0100
Re: Did I encode Sipser correctly? (it seemed too easy) Ben Bacarisse <ben.usenet@bsb.me.uk> - 2022-07-10 00:04 +0100
Re: Did I encode Sipser correctly? (it seemed too easy) olcott <NoOne@NoWhere.com> - 2022-07-09 18:36 -0500
Re: Did I encode Sipser correctly? (it seemed too easy) André G. Isaak <agisaak@gm.invalid> - 2022-07-09 17:49 -0600
Re: Did I encode Sipser correctly? (it seemed too easy) olcott <NoOne@NoWhere.com> - 2022-07-09 19:08 -0500
Re: Did I encode Sipser correctly? (it seemed too easy) André G. Isaak <agisaak@gm.invalid> - 2022-07-09 19:04 -0600
Re: Did I encode Sipser correctly? (it seemed too easy) olcott <NoOne@NoWhere.com> - 2022-07-09 20:41 -0500
Re: Did I encode Sipser correctly? (it seemed too easy) Richard Damon <Richard@Damon-Family.org> - 2022-07-09 21:56 -0400
Re: Did I encode Sipser correctly? (it seemed too easy) André G. Isaak <agisaak@gm.invalid> - 2022-07-09 20:04 -0600
Re: Did I encode Sipser correctly? (it seemed too easy) olcott <NoOne@NoWhere.com> - 2022-07-09 21:21 -0500
Re: Did I encode Sipser correctly? (it seemed too easy) Richard Damon <Richard@Damon-Family.org> - 2022-07-09 22:50 -0400
Re: Did I encode Sipser correctly? (it seemed too easy) "dklei...@gmail.com" <dkleinecke@gmail.com> - 2022-07-09 19:20 -0700
Re: Did I encode Sipser correctly? (it seemed too easy) olcott <NoOne@NoWhere.com> - 2022-07-09 21:34 -0500
Re: Did I encode Sipser correctly? (it seemed too easy) André G. Isaak <agisaak@gm.invalid> - 2022-07-09 20:46 -0600
Re: Did I encode Sipser correctly? (it seemed too easy) olcott <NoOne@NoWhere.com> - 2022-07-09 22:48 -0500
Re: Did I encode Sipser correctly? (it seemed too easy) Richard Damon <Richard@Damon-Family.org> - 2022-07-10 07:15 -0400
Re: Did I encode Sipser correctly? (it seemed too easy) Richard Damon <Richard@Damon-Family.org> - 2022-07-09 23:00 -0400
Re: Did I encode Sipser correctly? (it seemed too easy) Richard Damon <Richard@Damon-Family.org> - 2022-07-09 20:42 -0400
Re: Did I encode Sipser correctly? (it seemed too easy) André G. Isaak <agisaak@gm.invalid> - 2022-07-09 18:57 -0600
Re: Did I encode Sipser correctly? (it seemed too easy) Richard Damon <Richard@Damon-Family.org> - 2022-07-09 21:39 -0400
Re: Did I encode Sipser correctly? (it seemed too easy) André G. Isaak <agisaak@gm.invalid> - 2022-07-09 20:15 -0600
Re: Did I encode Sipser correctly? (it seemed too easy) olcott <NoOne@NoWhere.com> - 2022-07-09 21:23 -0500
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
Re: Did I encode Sipser correctly? (it seemed too easy) Mikko <mikko.levanto@iki.fi> - 2022-07-10 15:26 +0300
Re: Did I encode Sipser correctly? (it seemed too easy) olcott <NoOne@NoWhere.com> - 2022-07-10 08:34 -0500
Re: Did I encode Sipser correctly? (it seemed too easy) Richard Damon <Richard@Damon-Family.org> - 2022-07-10 17:30 -0400
Re: Did I encode Sipser correctly? (it seemed too easy) Mikko <mikko.levanto@iki.fi> - 2022-07-12 16:09 +0300
Re: Did I encode Sipser correctly? (it seemed too easy) olcott <NoOne@NoWhere.com> - 2022-07-12 08:13 -0500
Re: Did I encode Sipser correctly? (it seemed too easy) Richard Damon <Richard@Damon-Family.org> - 2022-07-12 19:03 -0400
Re: Did I encode Sipser correctly? (it seemed too easy) olcott <polcott2@gmail.com> - 2022-07-13 07:45 -0500
Re: Did I encode Sipser correctly? (it seemed too easy) Mikko <mikko.levanto@iki.fi> - 2022-07-13 16:47 +0300
Re: Did I encode Sipser correctly? (it seemed too easy) olcott <NoOne@NoWhere.com> - 2022-07-13 09:49 -0500
Re: Did I encode Sipser correctly? (it seemed too easy) Richard Damon <Richard@Damon-Family.org> - 2022-07-13 18:47 -0400
Re: Did I encode Sipser correctly? (it seemed too easy) Richard Damon <Richard@Damon-Family.org> - 2022-07-13 18:43 -0400
Re: Did I encode Sipser correctly? (it seemed too easy) Mikko <mikko.levanto@iki.fi> - 2022-07-20 10:48 +0300
Re: Did I encode Sipser correctly? (it seemed too easy) Richard Damon <Richard@Damon-Family.org> - 2022-07-20 07:16 -0400
Re: Did I encode Sipser correctly? (it seemed too easy) Mikko <mikko.levanto@iki.fi> - 2022-07-20 17:33 +0300
Re: Did I encode Sipser correctly? (it seemed too easy) Richard Damon <Richard@Damon-Family.org> - 2022-07-20 18:50 -0400
csiph-web