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


Groups > comp.theory > #25160

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-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>

Show all headers | View raw


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


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