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.

The Sipser proof has the same Liar Paradox pathological
self-reference(Olcott 2004).

Now we construct a new Turing machine D with H as a subroutine. This new
TM calls H to determine what M does when the input to M is its own
description ⟨M⟩. Once D has determined this information, it does the
opposite. That is, it rejects if M accepts and accepts if M does not
accept. The following is a description of D:

D(⟨M⟩) = { accept if M does not accept ⟨M⟩
{ reject if M accepts ⟨M⟩

http://www.liarparadox.org/Sipser_165_167.pdf

--
Copyright 2021 Pete Olcott

"Great spirits have always encountered violent opposition from mediocre
minds." Einstein

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.

/Flibble

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

On 7/15/2021 12:48 PM, Mr Flibble 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.
>
> /Flibble
>

If you check with Mike, Ben and Kaz they will all tell you that the
halting problem is considered undecidable because of the pathlogical input.

--
Copyright 2021 Pete Olcott

"Great spirits have always encountered violent opposition from mediocre
minds." Einstein

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.

--
Copyright 2021 Pete Olcott

"Great spirits have always encountered violent opposition from mediocre
minds." Einstein

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

On 7/15/2021 1:09 PM, Mr Flibble wrote:
> 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
>

I address the Peter Linz instance of that at the end of my paper:
https://www.researchgate.net/publication/351947980_Halting_problem_undecidability_and_infinitely_nested_simulation

It is still very obviously infinitely nested simulation.
It is merely more difficult for the halt decider to detect.

--
Copyright 2021 Pete Olcott

"Great spirits have always encountered violent opposition from mediocre
minds." Einstein