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

Groups > comp.software-eng > #3107 > unrolled thread

Re: Halting problem erroneously defined

Back to article view | Back to comp.software-eng

This discussion starts older than the indexed window; earlier articles aren't shown. The article labeled Started by below is the oldest one visible, not the original post.

Contents

  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

#3107 — Re: Halting problem erroneously defined

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

[toc] | [next] | [standalone]

#3108

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

[toc] | [prev] | [next] | [standalone]

#3109

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

[toc] | [prev] | [next] | [standalone]

#3111

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

[toc] | [prev] | [next] | [standalone]

#3112

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

[toc] | [prev] | [next] | [standalone]

#3113

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

[toc] | [prev] | [next] | [standalone]

#3110

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

[toc] | [prev] | [standalone]

Back to top | Article view | comp.software-eng

csiph-web