Re: Halting problem erroneously defined

From	Mr Flibble <flibble@reddwarf.jmc>
Newsgroups	comp.theory
Subject	Re: Halting problem erroneously defined
Message-ID	<20210716133319.000033a8@reddwarf.jmc> (permalink)
References	<20210715182217.00002c8c@reddwarf.jmc> <yKudnbQsIpYNGm39nZ2dnUU78R_NnZ2d@brightview.co.uk>
Organization	Jupiter Mining Corp
Date	2021-07-16 13:33 +0100

Show all headers | View raw

On Thu, 15 Jul 2021 20:08:00 +0100
Mike Terry <news.dead.person.stones@darjeeling.plus.com> wrote:

> On 15/07/2021 18:22, Mr Flibble wrote:
> > Hi!
> > 
> >  From Wikipedia Halting Problem page:
> > 
> > 	For any program f that might determine if programs halt, a
> > 	"pathological" program g, called with some input, can pass
> > its own source and its input to f and then specifically do the
> > 	opposite of what f predicts g will do. No f can exist that
> > 	handles this case.  
> 
> Well, that's awful wording, because it's liable to give readers the 
> impression that some specific g exists which no decider could decide 
> correctly.  That would be nonsense - the fact is that g is derived
> from f, so it would be better to call it N(f) or something [N for
> Nemesis!].
> 
> Then we could say clearly that no f can exist that handles its own
> N(f) case.  This implies that every f gets at least one input wrong
> (e.g. N(f)), so no f can correctly decide halting for all inputs.
> 
> Note that it's the ORDER of choices which is important:  FIRST f is 
> fixed, THEN  N(f) becomes defined (fixed) as a consequence, and f 
> decides N(f) incorrectly.  (Another decider h may decide N(f)
> correctly, but of course that h won't decide N(h) correctly and so
> on.)
> 
> > 
> > To me this looks like everyone is assuming that the halting problem
> > is undecidable based on a misunderstanding of the contradiction
> > crystallized by [Strachen 1965].  
> 
> Do you have a link for [Strachen 1965]?  The only link I've been able
> to find is a short letter of just three paragraphs, here:
> 
>    <https://academic.oup.com/comjnl/article/7/4/313/354243>
> 
> I'll assume that's what you're referring to??
> 
> > 
> > Strachen isn't saying the halting problem is undecidable,   
> 
> Dude, YES HE IS:
> Quote:
>    This left me with an uneasy feeling that the proof must be long
>    and complicated, but in fact it is so short and simple it may be
>    of interest to casual readers.
> 
> HE'S CONFIRMING THAT THE THEOREM IS CORRECT, and has a short proof
> which he then outlines!

NO HE ISN'T. He is saying that T cannot exist as a decider of P because
P is aware of T and attempts to defeat it; this DOES NOT MEAN that a T
cannot decide P where P isn't attempting to defeat T by recursively
referencing it. This is why Strachen refers to is as an "impossible
program".

/Flibble

Thread

Halting problem erroneously defined Mr Flibble <flibble@reddwarf.jmc> - 2021-07-15 18:22 +0100
  Re: Halting problem erroneously defined olcott <NoOne@NoWhere.com> - 2021-07-15 12:42 -0500
    Re: Halting problem erroneously defined Mr Flibble <flibble@reddwarf.jmc> - 2021-07-15 18:48 +0100
      Re: Halting problem erroneously defined Mr Flibble <flibble@reddwarf.jmc> - 2021-07-15 19:00 +0100
        Re: Halting problem erroneously defined olcott <NoOne@NoWhere.com> - 2021-07-15 13:04 -0500
          Re: Halting problem erroneously defined Mr Flibble <flibble@reddwarf.jmc> - 2021-07-15 19:09 +0100
            Re: Halting problem erroneously defined olcott <NoOne@NoWhere.com> - 2021-07-15 13:17 -0500
      Re: Halting problem erroneously defined olcott <NoOne@NoWhere.com> - 2021-07-15 13:01 -0500
  Re: Halting problem erroneously defined Mike Terry <news.dead.person.stones@darjeeling.plus.com> - 2021-07-15 20:08 +0100
    Re: Halting problem erroneously defined olcott <NoOne@NoWhere.com> - 2021-07-15 15:57 -0500
      Re: Halting problem erroneously defined Ben Bacarisse <ben.usenet@bsb.me.uk> - 2021-07-15 23:06 +0100
        Re: Halting problem erroneously defined olcott <NoOne@NoWhere.com> - 2021-07-15 18:00 -0500
          Re: Halting problem erroneously defined Ben Bacarisse <ben.usenet@bsb.me.uk> - 2021-07-16 01:29 +0100
            Re: Halting problem erroneously defined olcott <NoOne@NoWhere.com> - 2021-07-15 19:59 -0500
              Re: Halting problem erroneously defined Ben Bacarisse <ben.usenet@bsb.me.uk> - 2021-07-16 02:49 +0100
                Re: Halting problem erroneously defined olcott <NoOne@NoWhere.com> - 2021-07-15 21:43 -0500
                Re: Halting problem erroneously defined Ben Bacarisse <ben.usenet@bsb.me.uk> - 2021-07-17 01:29 +0100
                Re: Halting problem erroneously defined olcott <NoOne@NoWhere.com> - 2021-07-17 11:05 -0500
                Re: Halting problem erroneously defined Ben Bacarisse <ben.usenet@bsb.me.uk> - 2021-07-18 02:36 +0100
                Re: Halting problem erroneously defined olcott <NoOne@NoWhere.com> - 2021-07-19 10:09 -0500
                Re: Halting problem erroneously defined Richard Damon <Richard@Damon-Family.org> - 2021-07-19 08:18 -0700
                Re: Halting problem erroneously defined Ben Bacarisse <ben.usenet@bsb.me.uk> - 2021-07-20 01:38 +0100
                Re: Halting problem erroneously defined olcott <NoOne@NoWhere.com> - 2021-07-20 09:29 -0500
                Re: Halting problem erroneously defined Richard Damon <Richard@Damon-Family.org> - 2021-07-20 09:17 -0700
                Re: Halting problem erroneously defined Ben Bacarisse <ben.usenet@bsb.me.uk> - 2021-07-21 01:28 +0100
                Re: Halting problem erroneously defined Richard Damon <Richard@Damon-Family.org> - 2021-07-17 21:57 -0600
    Re: Halting problem erroneously defined Mr Flibble <flibble@reddwarf.jmc> - 2021-07-16 13:25 +0100
      Re: Halting problem erroneously defined olcott <NoOne@NoWhere.com> - 2021-07-16 08:56 -0500
    Re: Halting problem erroneously defined Mr Flibble <flibble@reddwarf.jmc> - 2021-07-16 13:33 +0100
      Re: Halting problem erroneously defined olcott <NoOne@NoWhere.com> - 2021-07-16 09:28 -0500
      Re: Halting problem erroneously defined Alan Mackenzie <acm@muc.de> - 2021-07-16 14:44 +0000
        Re: Halting problem erroneously defined olcott <NoOne@NoWhere.com> - 2021-07-16 09:52 -0500
          Re: Halting problem erroneously defined Alan Mackenzie <acm@muc.de> - 2021-07-16 16:39 +0000
            Re: Halting problem erroneously defined olcott <NoOne@NoWhere.com> - 2021-07-16 12:13 -0500
              Re: Halting problem erroneously defined Mr Flibble <flibble@reddwarf.jmc> - 2021-07-16 18:26 +0100
                Re: Halting problem erroneously defined olcott <NoOne@NoWhere.com> - 2021-07-16 12:41 -0500
                Re: Halting problem erroneously defined Ben Bacarisse <ben.usenet@bsb.me.uk> - 2021-07-16 19:37 +0100
              Re: Halting problem erroneously defined André G. Isaak <agisaak@gm.invalid> - 2021-07-16 11:53 -0600
                Re: Halting problem erroneously defined olcott <NoOne@NoWhere.com> - 2021-07-16 13:39 -0500
                Re: Halting problem erroneously defined André G. Isaak <agisaak@gm.invalid> - 2021-07-16 12:52 -0600
                Re: Halting problem erroneously defined olcott <NoOne@NoWhere.com> - 2021-07-16 14:40 -0500
                Re: Halting problem erroneously defined André G. Isaak <agisaak@gm.invalid> - 2021-07-16 13:57 -0600
                Re: Halting problem erroneously defined olcott <NoOne@NoWhere.com> - 2021-07-16 15:09 -0500
                Re: Halting problem erroneously defined André G. Isaak <agisaak@gm.invalid> - 2021-07-16 14:30 -0600
                Re: Halting problem erroneously defined olcott <NoOne@NoWhere.com> - 2021-07-16 16:06 -0500
                Re: Halting problem erroneously defined André G. Isaak <agisaak@gm.invalid> - 2021-07-16 16:09 -0600
                Re: Halting problem erroneously defined olcott <NoOne@NoWhere.com> - 2021-07-16 17:24 -0500
                Re: Halting problem erroneously defined André G. Isaak <agisaak@gm.invalid> - 2021-07-16 16:48 -0600
                Re: Halting problem erroneously defined olcott <NoOne@NoWhere.com> - 2021-07-17 10:22 -0500
                Re: Halting problem erroneously defined Richard Damon <Richard@Damon-Family.org> - 2021-07-17 22:24 -0600
                Re: Halting problem erroneously defined Richard Damon <Richard@Damon-Family.org> - 2021-07-17 22:09 -0600
                Re: Halting problem erroneously defined Jeff Barnett <jbb@notatt.com> - 2021-07-16 13:51 -0600
                Re: Halting problem erroneously defined olcott <NoOne@NoWhere.com> - 2021-07-16 14:57 -0500
                Re: Halting problem erroneously defined Jeff Barnett <jbb@notatt.com> - 2021-07-16 16:34 -0600
              Re: Halting problem erroneously defined Alan Mackenzie <acm@muc.de> - 2021-07-16 18:25 +0000
                Re: Halting problem erroneously defined Mr Flibble <flibble@reddwarf.jmc> - 2021-07-16 19:29 +0100
                Re: Halting problem erroneously defined Alan Mackenzie <acm@muc.de> - 2021-07-16 18:59 +0000
                Re: Halting problem erroneously defined olcott <NoOne@NoWhere.com> - 2021-07-16 14:42 -0500
                Re: Halting problem erroneously defined olcott <NoOne@NoWhere.com> - 2021-07-16 14:22 -0500
                Re: Halting problem erroneously defined olcott <NoOne@NoWhere.com> - 2021-07-16 14:33 -0500
                Re: Halting problem erroneously defined Alan Mackenzie <acm@muc.de> - 2021-07-16 20:19 +0000
                Re: Halting problem erroneously defined olcott <NoOne@NoWhere.com> - 2021-07-16 15:34 -0500
                Re: Halting problem erroneously defined Alan Mackenzie <acm@muc.de> - 2021-07-16 21:30 +0000
                Re: Halting problem erroneously defined olcott <NoOne@NoWhere.com> - 2021-07-16 16:57 -0500
                Re: Halting problem erroneously defined Alan Mackenzie <acm@muc.de> - 2021-07-17 09:39 +0000
                Re: Halting problem erroneously defined [AM] olcott <NoOne@NoWhere.com> - 2021-07-17 10:11 -0500
                Re: Halting problem erroneously defined [AM] Alan Mackenzie <acm@muc.de> - 2021-07-17 17:41 +0000
                Re: Halting problem erroneously defined [AM] olcott <NoOne@NoWhere.com> - 2021-07-17 13:26 -0500
              Re: Halting problem erroneously defined wij <wyniijj@gmail.com> - 2021-07-16 11:45 -0700
                Re: Halting problem erroneously defined olcott <NoOne@NoWhere.com> - 2021-07-16 14:37 -0500
                Re: Halting problem erroneously defined Richard Damon <Richard@Damon-Family.org> - 2021-07-17 22:28 -0600
              Re: Halting problem erroneously defined Jeff Barnett <jbb@notatt.com> - 2021-07-16 13:31 -0600
          Re: Halting problem erroneously defined Richard Damon <Richard@Damon-Family.org> - 2021-07-17 22:06 -0600
  Re: Halting problem erroneously defined wij <wyniijj@gmail.com> - 2021-07-17 03:01 -0700
  Re: Halting problem erroneously defined Charlie-Boo <shymathguy@gmail.com> - 2021-07-19 07:35 -0700
    Re: Halting problem erroneously defined olcott <NoOne@NoWhere.com> - 2021-07-19 15:45 -0500
      Re: Halting problem erroneously defined Richard Damon <Richard@Damon-Family.org> - 2021-07-19 20:44 -0700
  Re: Halting problem erroneously defined Charlie-Boo <shymathguy@gmail.com> - 2021-07-19 07:43 -0700
    Re: Halting problem erroneously defined olcott <NoOne@NoWhere.com> - 2021-07-19 15:49 -0500
      Re: Halting problem erroneously defined Richard Damon <Richard@Damon-Family.org> - 2021-07-19 20:46 -0700

csiph-web