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

Groups > comp.software-eng > #3109

Re: Halting problem erroneously defined

Cross-posted to 4 groups.

Show all headers | View raw

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

Back to comp.software-eng | Previous | Next — Previous in thread | Next in thread | Find similar | Unroll thread

Thread

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

csiph-web