XPost: comp.theory, comp.ai.philosophy, comp.software-eng
From: flibble@reddwarf.jmc
On Thu, 15 Jul 2021 12:42:22 -0500
olcott 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 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.
/Flibble
--- SoupGate-Win32 v1.05
* Origin: you cannot sedate... all the things you hate (1:229/2)
|
