Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]
| From | Ben Bacarisse <ben.usenet@bsb.me.uk> |
|---|---|
| Newsgroups | comp.theory |
| Subject | Re: A non-halting decider is defined [ 2020-11-11 version ] |
| Date | 2020-11-12 01:00 +0000 |
| Organization | A noiseless patient Spider |
| Message-ID | <87tutvs824.fsf@bsb.me.uk> (permalink) |
| References | (4 earlier) <4RXqH.261071$d95.207052@fx06.iad> <81b63906-3740-4840-abe3-acfbec62209do@googlegroups.com> <3eKdnTKBs4GCwjHCnZ2dnUU78N-dnZ2d@brightview.co.uk> <87k0urtpr5.fsf@bsb.me.uk> <K6udnSQtUoWU4THCnZ2dnUU7-T3NnZ2d@giganews.com> |
olcott <NoOne@NoWhere.com> writes: > On 11/11/2020 5:53 PM, Ben Bacarisse wrote: >> Mike Terry <news.dead.person.stones@darjeeling.plus.com> writes: >> >>> On 11/11/2020 21:00, David Kleinecke wrote: >> <cut> >>>> But all that is required is to provide the code for a universal >>>> halt detector in any old language. For a while now what proports >>>> to be the code of such a detector has been posted and copied. It >>>> is a joke - a wrapper around two programs that apparently someone >>>> thinks do the work of a universal halt detector. >>>> >>> >>> PO is not claiming to have a /universal/ halt detector. >> >> Not so long ago: >> >> "The non-halting decider that I defined accepts any and all >> non-halting inputs and rejects any and all halting inputs." >> >> That is a universal halt decider. It's true that recent posts have >> mentioned partial deciders, but he's never retracted it (as if!). >> >>> Linz's proof goes along these lines: >>> 1) Suppose H is a universal halt decider >>> 2) Construct from H this new program H^. [Details in Linz proof, >>> but crucially, /every/ H has its own corresponding H^.] >>> 3) Then we show that due to the way H^ was constructed from H, >>> H incorrectly decides halting for the input pair (H^, H^). >>> [..contradicting (1)] >> >> I wonder if PO would have wasted so much time if the proof had been >> written differently. As I am sure you know, step 1 is not needed. You >> can reason about any TM, M, and show that is does not compute the >> halting function because either there is some i for which M(i) does not >> terminate, or there is some i for which M(i) =/= halts(i). >> >> In fact Linz shows this proof for historical reasons only. Having >> established, in the previous chapter, that there is a recursively >> enumerable language that is not recursive, the halting theorem is proved >> as a one-sentence corollary of that. Unfortunately PO has not read the >> book. > > If the conventional: > "Do the opposite of whatever the halt decider decides" ** > > trick is shown to be decidable, then what is left that shows that > halting is undecidable? All the other proofs you have not read. For example the tiny proof that directly follows the pages of Linz you have obsessed about for so many years. And of course there is the proof via Rado's demonstration that the BB function is not computable. You have a real problem understanding the notion of a proof. There were dozens of published "proofs" of the four colour theorem, all of which were shown to be wrong. It's still a theorem, though, because there is a valid proof of it. Only one is needed no matter how many non-proofs there are. Hypotheticals aside, you remain wrong about the main point. H gets H(H_Hat, H_Hat) wrong because the answer conflicts with the nature of the computation H_Hat(H_Hat). Neither what your H "had to do", nor what H_Hat "would do" were is ever so slightly different, make the wrong answer right. It's amazing that you keep going despite accepting the plain facts of the matter: that H(H_Hat, H_Hat) is false and that H_Hat(H_Hat) is a finite computation. -- Ben.
Back to comp.theory | Previous | Next — Previous in thread | Next in thread | Find similar | Unroll thread
A non-halting decider is defined olcott <NoOne@NoWhere.com> - 2020-10-28 18:43 -0500
Re: Stop crossposting you imbecil spammer (Re: A non-halting decider is defined Mostowski Collapse <janburse@fastmail.fm> - 2020-10-29 19:40 +0100
Re: A non-halting decider is defined [ 2020-11-11 version ] olcott <NoOne@NoWhere.com> - 2020-11-11 11:06 -0600
Re: A non-halting decider is defined [ 2020-11-11 version ] Mike Terry <news.dead.person.stones@darjeeling.plus.com> - 2020-11-11 18:11 +0000
Re: A non-halting decider is defined [ 2020-11-11 version ] David Kleinecke <dkleinecke@gmail.com> - 2020-11-11 10:59 -0800
Re: A non-halting decider is defined [ 2020-11-11 version ] olcott <NoOne@NoWhere.com> - 2020-11-11 13:08 -0600
Re: A non-halting decider is defined [ 2020-11-11 version ] Richard Damon <Richard@Damon-Family.org> - 2020-11-11 15:29 -0500
Re: A non-halting decider is defined [ 2020-11-11 version ] David Kleinecke <dkleinecke@gmail.com> - 2020-11-11 13:00 -0800
Re: A non-halting decider is defined [ 2020-11-11 version ] olcott <NoOne@NoWhere.com> - 2020-11-11 15:56 -0600
Re: A non-halting decider is defined [ 2020-11-11 version ] Mike Terry <news.dead.person.stones@darjeeling.plus.com> - 2020-11-11 22:01 +0000
Re: A non-halting decider is defined [ 2020-11-11 version ] olcott <NoOne@NoWhere.com> - 2020-11-11 17:48 -0600
Re: A non-halting decider is defined [ 2020-11-11 version ] Jeff Barnett <jbb@notatt.com> - 2020-11-11 17:33 -0700
Re: A non-halting decider is defined [ 2020-11-11 version ] Mike Terry <news.dead.person.stones@darjeeling.plus.com> - 2020-11-12 02:02 +0000
Re: A non-halting decider is defined [ 2020-11-11 version ] Ben Bacarisse <ben.usenet@bsb.me.uk> - 2020-11-11 23:53 +0000
Re: A non-halting decider is defined [ 2020-11-11 version ] olcott <NoOne@NoWhere.com> - 2020-11-11 18:04 -0600
Re: A non-halting decider is defined [ 2020-11-11 version ] Ben Bacarisse <ben.usenet@bsb.me.uk> - 2020-11-12 01:00 +0000
Re: A non-halting decider is defined [ 2020-11-11 version ] olcott <NoOne@NoWhere.com> - 2020-11-11 19:16 -0600
Re: A non-halting decider is defined [ 2020-11-11 version ] Richard Damon <Richard@Damon-Family.org> - 2020-11-11 19:00 -0500
Re: A non-halting decider is defined [ 2020-11-11 version ] olcott <NoOne@NoWhere.com> - 2020-11-11 18:11 -0600
Re: A non-halting decider is defined [ 2020-11-11 version ] Richard Damon <Richard@Damon-Family.org> - 2020-11-11 20:44 -0500
Re: A non-halting decider is defined [ 2020-11-11 version ] olcott <NoOne@NoWhere.com> - 2020-11-11 19:52 -0600
Re: A non-halting decider is defined [ 2020-11-11 version ] Richard Damon <Richard@Damon-Family.org> - 2020-11-11 21:06 -0500
Re: A non-halting decider is defined [ count-example? ] olcott <NoOne@NoWhere.com> - 2020-11-14 08:09 -0600
Re: A non-halting decider is defined Mr Flibble <flibbleREMOVETHISBIT@i42.co.uk> - 2020-11-12 18:36 +0000
Re: A non-halting decider is defined Sjouke Burry <burrynulnulfour@ppllaanneett.nnll> - 2020-11-12 21:37 +0100
Re: A non-halting decider is defined olcott <NoOne@NoWhere.com> - 2020-11-12 14:59 -0600
csiph-web