Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]


Groups > comp.theory > #25150

Re: A non-halting decider is defined [ 2020-11-11 version ]

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>

Show all headers | View raw


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


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