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

Groups > comp.theory > #36350

Re: Halting problem erroneously defined

From Mr Flibble <flibble@reddwarf.jmc>
Newsgroups comp.theory, comp.ai.philosophy, comp.software-eng, sci.math.symbolic
Subject Re: Halting problem erroneously defined
Message-ID <20210715190910.00004af7@reddwarf.jmc> (permalink)
References <20210715182217.00002c8c@reddwarf.jmc> <--GdnXjxI_zg7m39nZ2dnUU7-f3NnZ2d@giganews.com> <20210715184801.00002697@reddwarf.jmc> <20210715190025.00005ac7@reddwarf.jmc> <n6CdndYR1eAk5W39nZ2dnUU7-dWdnZ2d@giganews.com>
Organization Jupiter Mining Corp
Date 2021-07-15 19:09 +0100

Cross-posted to 4 groups.

Show all headers | View raw

On Thu, 15 Jul 2021 13:04:42 -0500
olcott <NoOne@NoWhere.com> wrote:

> On 7/15/2021 1:00 PM, Mr Flibble wrote:
> > On Thu, 15 Jul 2021 18:48:01 +0100
> > Mr Flibble <flibble@reddwarf.jmc> wrote:
> >   
> >> On Thu, 15 Jul 2021 12:42:22 -0500
> >> olcott <NoOne@NoWhere.com> wrote:
> >>  
> >>> On 7/15/2021 12:22 PM, 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.
> >>>>
> >>>> 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].
> >>>>
> >>>> Strachen isn't saying the halting problem is undecidable, he is
> >>>> saying that there is a contradiction that means that a decider
> >>>> can not be a part of or called by that which is being decided.
> >>>> This doesn't mean that the halting problem is not undecidable
> >>>> but it does mean that if that Wikipedia extract is the current
> >>>> state of the art then nobody has proven that the HP is
> >>>> undecidable, at least for non-"pathological" programs.
> >>>>
> >>>> Olcott is on to something. :)
> >>>>
> >>>> /Flibble
> >>>>        
> >>>
> >>> I am really glad that you are back.
> >>> Strachen <is> saying that the halting problem is undecidable.  
> >>
> >> No he isn't he is saying a decider cannot decide a program that is
> >> aware of the decider, i.e. is "pathological". So, given two things:
> >>
> >> (1) a decider that can decide non-pathological programs, and
> >> (2) a decider that can detect if a program is pathological (i.e. is
> >> aware of the decider),
> >>
> >> then:
> >>
> >> the halting problem becomes decidable.
> >>
> >> Unless I am missing something.  
> > 
> > Of course for (2) to be feasible the decider would probably have to
> > be a black box .. but I am HP newbie so I am merely thinking out
> > loud. :D
> > 
> > /Flibble
> >   
> 
> My halt decider does correctly decide the pathological input by first 
> removing the pathology. H isolates itself from having any effect on
> its halt status decision by only acting as a pure simulator of its
> input until after its halt status decision has been made.
 
Unless I am mistaken you can't do that: the candidate program can call a
function EQUIVALENT (i.e. different implementation but same result) as
your decider; you would need to be able to detect such an equivalence.

/Flibble

Back to comp.theory | Previous | Next — Previous in thread | Next in thread | Find similar | Unroll thread

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