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-11 23:53 +0000 |
| Organization | A noiseless patient Spider |
| Message-ID | <87k0urtpr5.fsf@bsb.me.uk> (permalink) |
| References | (2 earlier) <tKednXr4xevQtDHCnZ2dnUU78T3NnZ2d@brightview.co.uk> <1904ff20-b029-4ca6-89b9-615f5984e00do@googlegroups.com> <4RXqH.261071$d95.207052@fx06.iad> <81b63906-3740-4840-abe3-acfbec62209do@googlegroups.com> <3eKdnTKBs4GCwjHCnZ2dnUU78N-dnZ2d@brightview.co.uk> |
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. -- 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