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

Groups > comp.theory > #36344 > unrolled thread

Halting problem erroneously defined

Back to article view | Back to comp.theory

Contents

  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

Page 1 of 4  [1] 2 3 4  Next page →

#36344 — Halting problem erroneously defined

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

[toc] | [next] | [standalone]

#36345

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] | [prev] | [next] | [standalone]

#36346

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]

#36347

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]

#36349

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]

#36350

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]

#36351

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]

#36348

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] | [next] | [standalone]

#36352

On 15/07/2021 18:22, 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.

Well, that's awful wording, because it's liable to give readers the 
impression that some specific g exists which no decider could decide 
correctly.  That would be nonsense - the fact is that g is derived from 
f, so it would be better to call it N(f) or something [N for Nemesis!].

Then we could say clearly that no f can exist that handles its own N(f) 
case.  This implies that every f gets at least one input wrong (e.g. 
N(f)), so no f can correctly decide halting for all inputs.

Note that it's the ORDER of choices which is important:  FIRST f is 
fixed, THEN  N(f) becomes defined (fixed) as a consequence, and f 
decides N(f) incorrectly.  (Another decider h may decide N(f) correctly, 
but of course that h won't decide N(h) correctly and so on.)

> 
> 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].

Do you have a link for [Strachen 1965]?  The only link I've been able to 
find is a short letter of just three paragraphs, here:

   <https://academic.oup.com/comjnl/article/7/4/313/354243>

I'll assume that's what you're referring to??

> 
> Strachen isn't saying the halting problem is undecidable, 

Dude, YES HE IS:
Quote:
   This left me with an uneasy feeling that the proof must be long
   and complicated, but in fact it is so short and simple it may be
   of interest to casual readers.

HE'S CONFIRMING THAT THE THEOREM IS CORRECT, and has a short proof which 
he then outlines!


> He 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. 

Dude, HE'S NOT SAYING THAT.

Quote:
   ...In each case T(P) has exactly the wrong value, and this
   contradiction SHOWS THAT THE FUNCTION T CANNOT EXIST.

[My CAPS.  T is the purported halt decider.]  Where does Strachen say 
anything about "a decider can not be a part of or called by that which 
is being decided"?

Get a grip!  JUST READ THE WORDS... :/


Mike.

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

#36357

On 7/15/2021 2:08 PM, Mike Terry wrote:
> On 15/07/2021 18:22, 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.
> 
> Well, that's awful wording, because it's liable to give readers the 
> impression that some specific g exists which no decider could decide 
> correctly.  That would be nonsense - the fact is that g is derived from 
> f, so it would be better to call it N(f) or something [N for Nemesis!].
> 
> Then we could say clearly that no f can exist that handles its own N(f) 
> case.  This implies that every f gets at least one input wrong (e.g. 
> N(f)), so no f can correctly decide halting for all inputs.
> 

It is the same freaking pathological self-reference(olcott 2004) as the 
liar paradox:

Peter Olcott  Sep 5, 2004, 11:21:57 AM
The Liar Paradox can be shown to be nothing more than
a incorrectly formed statement because of its pathological
self-reference. The Halting Problem can only exist because
of this same sort of pathological self-reference.
https://groups.google.com/g/comp.theory/c/RO9Z9eCabeE/m/Ka8-xS2rdEEJ

> Note that it's the ORDER of choices which is important:  FIRST f is 
> fixed, THEN  N(f) becomes defined (fixed) as a consequence, and f 
> decides N(f) incorrectly.  (Another decider h may decide N(f) correctly, 
> but of course that h won't decide N(h) correctly and so on.)
> 
>>
>> 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].
> 
> Do you have a link for [Strachen 1965]?  The only link I've been able to 
> find is a short letter of just three paragraphs, here:
> 
>    <https://academic.oup.com/comjnl/article/7/4/313/354243>
> 
> I'll assume that's what you're referring to??

That is all there is to it. Apparently Strachen is responsible for the 
simplification found in all the modern proofs. He wrote his proof in the 
CPL language that he created, ancestor to BCPL, B and C.

>>
>> Strachen isn't saying the halting problem is undecidable, 
> 
> Dude, YES HE IS:
> Quote:
>    This left me with an uneasy feeling that the proof must be long
>    and complicated, but in fact it is so short and simple it may be
>    of interest to casual readers.
> 
> HE'S CONFIRMING THAT THE THEOREM IS CORRECT, and has a short proof which 
> he then outlines!
> 

Of this we agree.
Flibble was trying to credit Strachen 1965 with Olcott 2004.

> 
>> He 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. 
> 
> Dude, HE'S NOT SAYING THAT.
> 
> Quote:
>    ...In each case T(P) has exactly the wrong value, and this
>    contradiction SHOWS THAT THE FUNCTION T CANNOT EXIST.
> 
> [My CAPS.  T is the purported halt decider.]  Where does Strachen say 
> anything about "a decider can not be a part of or called by that which 
> is being decided"?
> 
> Get a grip!  JUST READ THE WORDS... :/
> 
> 
> Mike.
> 


He does have a deeper understanding of the malformed nature of the HP 
better than anyone besides me. It has the exactly same 
self-contradiction as the liar paradox.

All the academicians in the world still do not even understand that the 
Liar Paradox is logically incoherent. I had to create minimal type 
theory to even formally express that error of the Liar Paradox:

P := ~True(LP)


https://www.researchgate.net/publication/331859461_Minimal_Type_Theory_YACC_BNF

-- 
Copyright 2021 Pete Olcott

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

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

#36359

olcott <NoOne@NoWhere.com> writes:

> It is the same freaking pathological self-reference(olcott 2004) as
> the liar paradox:
>
> Peter Olcott  Sep 5, 2004, 11:21:57 AM

The halting problem is not like the liar paradox in that every program P
either does or does not halt when given input I.  The question of
whether P(I) halts always has a correct answer.  The fact that you have
been wrong about this for a very long time does not add weight to your
claim.

> ... Apparently Strachen

It's Strachey.  Christopher Strachey.  First professor of Computation at
Oxford.  Founder of the Oxford Programming Research Group.  Co-founder
of the influential field of denotational semantics.  Arguably the
inventor of time sharing systems.  He is worthy of at least sufficient
respect to pay attention to his name.

> is responsible for the
> simplification found in all the modern proofs.

I know of no proof that uses his sketch.  All the proofs are about some
formal model of computation.  What an irony, though, that the subject he
is most famous for (and you are apparently ignorant of) would actually
allow a proof based on pseudo-code, or, indeed, on something like CPL
running on an unbounded computer.  But, as I say, I don't know of one
done this way.

> He wrote his proof in

It's not a proof.

-- 
Ben.

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

#36362

On 7/15/2021 5:06 PM, Ben Bacarisse wrote:
> olcott <NoOne@NoWhere.com> writes:
> 
>> It is the same freaking pathological self-reference(olcott 2004) as
>> the liar paradox:
>>
>> Peter Olcott  Sep 5, 2004, 11:21:57 AM
> 
> The halting problem is not like the liar paradox in that every program P
> either does or does not halt when given input I.  

It is exactly like the liar paradox in one crucial way:

The Liar paradox is neither true nor false because both true and false 
values are contradicted.

> The question of
> whether P(I) halts always has a correct answer.  The fact that you have
> been wrong about this for a very long time does not add weight to your
> claim.
> 
>> ... Apparently Strachen
> 
> It's Strachey.  Christopher Strachey.  First professor of Computation at
> Oxford.  Founder of the Oxford Programming Research Group.  Co-founder
> of the influential field of denotational semantics.  Arguably the
> inventor of time sharing systems.  He is worthy of at least sufficient
> respect to pay attention to his name.
> 
>> is responsible for the
>> simplification found in all the modern proofs.
> 
> I know of no proof that uses his sketch.  All the proofs are about some
> formal model of computation.  

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.  http://www.liarparadox.org/sipser_165.pdf

All the modern proofs are based on an input doing the opposite of 
whatever its decider decides.

> What an irony, though, that the subject he
> is most famous for (and you are apparently ignorant of) would actually
> allow a proof based on pseudo-code, or, indeed, on something like CPL
> running on an unbounded computer.  But, as I say, I don't know of one
> done this way.
> 
>> He wrote his proof in
> 
> It's not a proof.
> 


-- 
Copyright 2021 Pete Olcott

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

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

#36366

olcott <NoOne@NoWhere.com> writes:

> On 7/15/2021 5:06 PM, Ben Bacarisse wrote:
>> olcott <NoOne@NoWhere.com> writes:
>> 
>>> It is the same freaking pathological self-reference(olcott 2004) as
>>> the liar paradox:
>>>
>>> Peter Olcott  Sep 5, 2004, 11:21:57 AM
>> The halting problem is not like the liar paradox in that every program P
>> either does or does not halt when given input I.  
>
> It is exactly like the liar paradox in one crucial way:
>
> The Liar paradox is neither true nor false because both true and false
> values are contradicted.

No.  If you've forgotten, just go back and read any of the posts I've
made over the last 16 years where I explain why that analogy is a false
one.  I used to repeat myself in case some innocent reader might take
you seriously, but I think all students reading this group will be able
to tell that you are, well, let's just say "confused".

> 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.  http://www.liarparadox.org/sipser_165.pdf
>
> All the modern proofs are based on an input doing the opposite of
> whatever its decider decides.

Some are.  I am glad you agree that what is in Sipser is a proof of the
theorem he states.  Can you move on now, or did you just use that word
by accident?

-- 
Ben.

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

#36369

On 7/15/2021 7:29 PM, Ben Bacarisse wrote:
> olcott <NoOne@NoWhere.com> writes:
> 
>> On 7/15/2021 5:06 PM, Ben Bacarisse wrote:
>>> olcott <NoOne@NoWhere.com> writes:
>>>
>>>> It is the same freaking pathological self-reference(olcott 2004) as
>>>> the liar paradox:
>>>>
>>>> Peter Olcott  Sep 5, 2004, 11:21:57 AM
>>> The halting problem is not like the liar paradox in that every program P
>>> either does or does not halt when given input I.
>>
>> It is exactly like the liar paradox in one crucial way:
>>
>> The Liar paradox is neither true nor false because both true and false
>> values are contradicted.
> 
> No.  If you've forgotten, just go back and read any of the posts I've
> made over the last 16 years where I explain why that analogy is a false
> one.  I used to repeat myself in case some innocent reader might take
> you seriously, but I think all students reading this group will be able
> to tell that you are, well, let's just say "confused".
> 

The aspect that in both cases their Boolean value is contradicted is the 
key analogous aspect.

Your God damned dishonest dodge fake rebuttal of pointing out there is 
another aspect where they are not analogous is what a lying cheating 
scoundrel would do to artificially contrive a fake rebuttal that would 
fool the gullible.

>> 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.  http://www.liarparadox.org/sipser_165.pdf
>>
>> All the modern proofs are based on an input doing the opposite of
>> whatever its decider decides.
> 
> Some are.  I am glad you agree that what is in Sipser is a proof of the
> theorem he states.  Can you move on now, or did you just use that word
> by accident?
> 

They are referred to as the proofs. If I referred to them as the halting 
problem misconceptions you would have no idea that I was referring to 
Sipser, Linz and Kozen.

-- 
Copyright 2021 Pete Olcott

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

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

#36370

olcott <NoOne@NoWhere.com> writes:

> On 7/15/2021 7:29 PM, Ben Bacarisse wrote:
>> olcott <NoOne@NoWhere.com> writes:
>> 
>>> On 7/15/2021 5:06 PM, Ben Bacarisse wrote:
>>>> olcott <NoOne@NoWhere.com> writes:
>>>>
>>>>> It is the same freaking pathological self-reference(olcott 2004) as
>>>>> the liar paradox:
>>>>>
>>>>> Peter Olcott  Sep 5, 2004, 11:21:57 AM
>>>> The halting problem is not like the liar paradox in that every program P
>>>> either does or does not halt when given input I.
>>>
>>> It is exactly like the liar paradox in one crucial way:
>>>
>>> The Liar paradox is neither true nor false because both true and false
>>> values are contradicted.
>> No.  If you've forgotten, just go back and read any of the posts I've
>> made over the last 16 years where I explain why that analogy is a false
>> one.  I used to repeat myself in case some innocent reader might take
>> you seriously, but I think all students reading this group will be able
>> to tell that you are, well, let's just say "confused".
>
> The aspect that in both cases their Boolean value is contradicted is
> the key analogous aspect.

You are deliberately vague about "the aspect" since you know full well
that every instance of the halting problem has a correct yes/no answer
which seems to be very different to the liar paradox.

In fact, in order to suggest a similarity you have to pretend that the
halting problem is not as I, and many other have stated it.

> Your God damned dishonest dodge fake rebuttal of pointing out there is
> another aspect where they are not analogous is what a lying cheating
> scoundrel would do to artificially contrive a fake rebuttal that would
> fool the gullible.

Get a grip, man!  Stating what the halting problem is and making it
clear that every instance has a correct yes/no answer is not rebutting
anything.  It's stating the issue so that you can choose to address it
if the fancy takes you.

>>> 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.  http://www.liarparadox.org/sipser_165.pdf
>>>
>>> All the modern proofs are based on an input doing the opposite of
>>> whatever its decider decides.
>> Some are.  I am glad you agree that what is in Sipser is a proof of the
>> theorem he states.  Can you move on now, or did you just use that word
>> by accident?
>
> They are referred to as the proofs. If I referred to them as the
> halting problem misconceptions you would have no idea that I was
> referring to Sipser, Linz and Kozen.

You need to find some way to say what you mean clearly.  In the past,
I've tried to help with that but you are not a fan of such posts so I
will leave it up to you.  If you don't consider them proofs, you should
not call them proofs.  If you do, readers are allowed to take you at
your word.

-- 
Ben.

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

#36372

On 7/15/2021 8:49 PM, Ben Bacarisse wrote:
> olcott <NoOne@NoWhere.com> writes:
> 
>> On 7/15/2021 7:29 PM, Ben Bacarisse wrote:
>>> olcott <NoOne@NoWhere.com> writes:
>>>
>>>> On 7/15/2021 5:06 PM, Ben Bacarisse wrote:
>>>>> olcott <NoOne@NoWhere.com> writes:
>>>>>
>>>>>> It is the same freaking pathological self-reference(olcott 2004) as
>>>>>> the liar paradox:
>>>>>>
>>>>>> Peter Olcott  Sep 5, 2004, 11:21:57 AM
>>>>> The halting problem is not like the liar paradox in that every program P
>>>>> either does or does not halt when given input I.
>>>>
>>>> It is exactly like the liar paradox in one crucial way:
>>>>
>>>> The Liar paradox is neither true nor false because both true and false
>>>> values are contradicted.
>>> No.  If you've forgotten, just go back and read any of the posts I've
>>> made over the last 16 years where I explain why that analogy is a false
>>> one.  I used to repeat myself in case some innocent reader might take
>>> you seriously, but I think all students reading this group will be able
>>> to tell that you are, well, let's just say "confused".
>>
>> The aspect that in both cases their Boolean value is contradicted is
>> the key analogous aspect.
> 
> You are deliberately vague about "the aspect" since you know full well
> that every instance of the halting problem has a correct yes/no answer
> which seems to be very different to the liar paradox.
> 

"This sentence is not true"
If the Liar Paradox is true that makes it true that it is not true AKA 
false.

If the Liar paradox is false that makes not true that it is not true AKA 
true.

If the C equivalent of the Strachey (1965) CPL returns true(halts) to P 
then P loops. If it returns false(does not halt) to P then P halts.

void P(u32 x)
{
   if (H(x, x))
     HERE: goto HERE;
}

int main()
{
   Output("Input_Halts = ", H((u32)P, (u32)P));
}

The self-contradiction of the halting problem counter-examples is 
apparently modeled after the liar paradox.

I continue to hope against hope that you simply misunderstand this and 
will eventually agree that I am correct. I think that the problem with 
this hope is that the enormous weight of evidence is on the side that 
you are a lying scoundrel about my halting problem insights.

> In fact, in order to suggest a similarity you have to pretend that the
> halting problem is not as I, and many other have stated it.
> 
>> Your God damned dishonest dodge fake rebuttal of pointing out there is
>> another aspect where they are not analogous is what a lying cheating
>> scoundrel would do to artificially contrive a fake rebuttal that would
>> fool the gullible.
> 
> Get a grip, man!  Stating what the halting problem is and making it
> clear that every instance has a correct yes/no answer is not rebutting
> anything.  It's stating the issue so that you can choose to address it
> if the fancy takes you.
> 
>>>> 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.  http://www.liarparadox.org/sipser_165.pdf
>>>>
>>>> All the modern proofs are based on an input doing the opposite of
>>>> whatever its decider decides.
>>> Some are.  I am glad you agree that what is in Sipser is a proof of the
>>> theorem he states.  Can you move on now, or did you just use that word
>>> by accident?
>>
>> They are referred to as the proofs. If I referred to them as the
>> halting problem misconceptions you would have no idea that I was
>> referring to Sipser, Linz and Kozen.
> 
> You need to find some way to say what you mean clearly.  In the past,
> I've tried to help with that but you are not a fan of such posts so I
> will leave it up to you.  If you don't consider them proofs, you should
> not call them proofs.  If you do, readers are allowed to take you at
> your word.
> 

The problem with that is that you simply ignore perfect clarity because 
perfect clarity is inconsistent with your goal of rebuttal:

The problem with that is that you simply ignore perfect clarity because 
perfect clarity is inconsistent with your goal of rebuttal:

The problem with that is that you simply ignore perfect clarity because 
perfect clarity is inconsistent with your goal of rebuttal:

You ask someone (we'll call him "Jack") to give a truthful
yes/no answer to the following question:

Will Jack's answer to this question be no?

Jack can't possibly give a correct yes/no answer to the question.
https://groups.google.com/g/sci.logic/c/4kIXI1kxmsI/m/hRroMoQZx2IJ
Daryl McCullough Jun 25, 2004, 6:30:39 PM

Daryl did not at the time appreciate that he provided the perfect 
analogy of the error of the halting problem. I contacted him very 
recently and it seems that he still does not understand this. His 
analogy goes into much greater depth with additional examples.

For Jack both yes and no are the wrong answer even though the question 
does have a correct answer when posed to other people it has no correct 
answer when posted to Jack.

-- 
Copyright 2021 Pete Olcott

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

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

#36483

olcott <NoOne@NoWhere.com> writes:

> On 7/15/2021 8:49 PM, Ben Bacarisse wrote:
>> olcott <NoOne@NoWhere.com> writes:
>> 
>>> On 7/15/2021 7:29 PM, Ben Bacarisse wrote:
>>>> olcott <NoOne@NoWhere.com> writes:
>>>>
>>>>> On 7/15/2021 5:06 PM, Ben Bacarisse wrote:
>>>>>> olcott <NoOne@NoWhere.com> writes:
>>>>>>
>>>>>>> It is the same freaking pathological self-reference(olcott 2004) as
>>>>>>> the liar paradox:
>>>>>>>
>>>>>>> Peter Olcott  Sep 5, 2004, 11:21:57 AM
>>>>>> The halting problem is not like the liar paradox in that every program P
>>>>>> either does or does not halt when given input I.
>>>>>
>>>>> It is exactly like the liar paradox in one crucial way:
>>>>>
>>>>> The Liar paradox is neither true nor false because both true and false
>>>>> values are contradicted.
>>>> No.  If you've forgotten, just go back and read any of the posts I've
>>>> made over the last 16 years where I explain why that analogy is a false
>>>> one.  I used to repeat myself in case some innocent reader might take
>>>> you seriously, but I think all students reading this group will be able
>>>> to tell that you are, well, let's just say "confused".
>>>
>>> The aspect that in both cases their Boolean value is contradicted is
>>> the key analogous aspect.
>>
>> You are deliberately vague about "the aspect" since you know full well
>> that every instance of the halting problem has a correct yes/no answer
>> which seems to be very different to the liar paradox.
>
> "This sentence is not true"
> If the Liar Paradox is true that makes it true that it is not true AKA false.
>
> If the Liar paradox is false that makes not true that it is not true AKA true.
>
> If the C equivalent of the Strachey (1965) CPL returns true(halts) to
> P then P loops. If it returns false(does not halt) to P then P halts.
>
> void P(u32 x)
> {
>   if (H(x, x))
>     HERE: goto HERE;
> }
>
> int main()
> {
>   Output("Input_Halts = ", H((u32)P, (u32)P));
> }
>
> The self-contradiction of the halting problem counter-examples is
> apparently modeled after the liar paradox.

P(P) (like all computations) either halts or it does not.  You tell us
it halts.  You also tell up that H(P,P) == 0.  H(P,P) == 0 is the wrong
answer for a halting computation.

> I continue to hope against hope that you simply misunderstand this and
> will eventually agree that I am correct.

I merely don't like your analogy.  Are there any facts in dispute?  I
think not.  If you find that the liar paradox helps to explain why your
H gets the wrong answer, then have at it.

> The problem with that is that you simply ignore perfect clarity
> because perfect clarity is inconsistent with your goal of rebuttal:

The facts of the matter are not in dispute.  For F to be a halt decider,
F(P, I) should be true iff P(I) halts and false otherwise.  Your H has
H(P,P) == false when P(I) halts.

Why you are wrong can be summed up in less then three lines stating just
a few of facts that you don't dispute.

-- 
Ben.

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

#36545

On 7/16/2021 7:29 PM, Ben Bacarisse wrote:
> olcott <NoOne@NoWhere.com> writes:
> 
>> On 7/15/2021 8:49 PM, Ben Bacarisse wrote:
>>> olcott <NoOne@NoWhere.com> writes:
>>>
>>>> On 7/15/2021 7:29 PM, Ben Bacarisse wrote:
>>>>> olcott <NoOne@NoWhere.com> writes:
>>>>>
>>>>>> On 7/15/2021 5:06 PM, Ben Bacarisse wrote:
>>>>>>> olcott <NoOne@NoWhere.com> writes:
>>>>>>>
>>>>>>>> It is the same freaking pathological self-reference(olcott 2004) as
>>>>>>>> the liar paradox:
>>>>>>>>
>>>>>>>> Peter Olcott  Sep 5, 2004, 11:21:57 AM
>>>>>>> The halting problem is not like the liar paradox in that every program P
>>>>>>> either does or does not halt when given input I.
>>>>>>
>>>>>> It is exactly like the liar paradox in one crucial way:
>>>>>>
>>>>>> The Liar paradox is neither true nor false because both true and false
>>>>>> values are contradicted.
>>>>> No.  If you've forgotten, just go back and read any of the posts I've
>>>>> made over the last 16 years where I explain why that analogy is a false
>>>>> one.  I used to repeat myself in case some innocent reader might take
>>>>> you seriously, but I think all students reading this group will be able
>>>>> to tell that you are, well, let's just say "confused".
>>>>
>>>> The aspect that in both cases their Boolean value is contradicted is
>>>> the key analogous aspect.
>>>
>>> You are deliberately vague about "the aspect" since you know full well
>>> that every instance of the halting problem has a correct yes/no answer
>>> which seems to be very different to the liar paradox.
>>
>> "This sentence is not true"
>> If the Liar Paradox is true that makes it true that it is not true AKA false.
>>
>> If the Liar paradox is false that makes not true that it is not true AKA true.
>>
>> If the C equivalent of the Strachey (1965) CPL returns true(halts) to
>> P then P loops. If it returns false(does not halt) to P then P halts.
>>
>> void P(u32 x)
>> {
>>    if (H(x, x))
>>      HERE: goto HERE;
>> }
>>
>> int main()
>> {
>>    Output("Input_Halts = ", H((u32)P, (u32)P));
>> }
>>
>> The self-contradiction of the halting problem counter-examples is
>> apparently modeled after the liar paradox.
> 
> P(P) (like all computations) either halts or it does not.  You tell us
> it halts.  You also tell up that H(P,P) == 0.  H(P,P) == 0 is the wrong
> answer for a halting computation.
> 

int main() { P(P); } specifies infinite recursion that it aborted at its 
third function call.

>> I continue to hope against hope that you simply misunderstand this and
>> will eventually agree that I am correct.
> 
> I merely don't like your analogy. 

Bullshit. You know that Daryl McCullough's analogy proves that I am 
right and you only want to prove me wrong even if you have to lie to 
make gullible fools believe that your rebuttal is valid.

https://groups.google.com/g/sci.logic/c/4kIXI1kxmsI/m/hRroMoQZx2IJ

>  Are there any facts in dispute?  I
> think not.  If you find that the liar paradox helps to explain why your
> H gets the wrong answer, then have at it.
> 
>> The problem with that is that you simply ignore perfect clarity
>> because perfect clarity is inconsistent with your goal of rebuttal:
> 
> The facts of the matter are not in dispute.  For F to be a halt decider,
> F(P, I) should be true iff P(I) halts and false otherwise.  Your H has
> H(P,P) == false when P(I) halts.
> 
> Why you are wrong can be summed up in less then three lines stating just
> a few of facts that you don't dispute.
> 

We must overcome rather than simply ignore the pathological 
self-reference(Olcott 2004) error:

Halt Deciding Axiom: When the pure simulation of the machine description 
⟨P⟩ of a machine P on its input I never halts we know that P(I) never 
halts.

Simulating halt decider H is only answering the question:
Would the input halt on its input if H never stopped simulating it?
(a) An answer of "no" universally means that the input never halts.
(b) An answer of "yes" universally means that the input halts.

The simulating halt decider must remain a pure simulator until after its 
halt status decision is made. This eliminates all pathological 
communication between the decider and its input.

-- 
Copyright 2021 Pete Olcott

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

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

#36574

olcott <NoOne@NoWhere.com> writes:

> On 7/16/2021 7:29 PM, Ben Bacarisse wrote:
>> olcott <NoOne@NoWhere.com> writes:

>>> If the C equivalent of the Strachey (1965) CPL returns true(halts) to
>>> P then P loops. If it returns false(does not halt) to P then P halts.
>>>
>>> void P(u32 x)
>>> {
>>>    if (H(x, x))
>>>      HERE: goto HERE;
>>> }
>>>
>>> int main()
>>> {
>>>    Output("Input_Halts = ", H((u32)P, (u32)P));
>>> }
>>>
>>> The self-contradiction of the halting problem counter-examples is
>>> apparently modeled after the liar paradox.
>>
>> P(P) (like all computations) either halts or it does not.  You tell us
>> it halts.  You also tell up that H(P,P) == 0.  H(P,P) == 0 is the wrong
>> answer for a halting computation. 
>
> int main() { P(P); } specifies infinite recursion that it aborted at
> its third function call.

P(P) halts (according to you).  H(P,P) == 0 (according to you).  That is
wrong (according to everyone but you).

>>> I continue to hope against hope that you simply misunderstand this and
>>> will eventually agree that I am correct.
>> I merely don't like your analogy. 
>
> Bullshit. You know that Daryl McCullough's analogy proves that I am
> right and you only want to prove me wrong even if you have to lie to
> make gullible fools believe that your rebuttal is valid.

Don't be silly.  You are wrong based on simple facts that you don't
dispute.  None of the facts are in dispute:

For H to be a halt decider, H(P,I) must be true if and only of P(I)
halts.  P(P) halts.  H(P,P) is false.

Three facts.  It's that simple.

-- 
Ben.

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

#36646

On 7/17/2021 8:36 PM, Ben Bacarisse wrote:
> olcott <NoOne@NoWhere.com> writes:
> 
>> On 7/16/2021 7:29 PM, Ben Bacarisse wrote:
>>> olcott <NoOne@NoWhere.com> writes:
> 
>>>> If the C equivalent of the Strachey (1965) CPL returns true(halts) to
>>>> P then P loops. If it returns false(does not halt) to P then P halts.
>>>>
>>>> void P(u32 x)
>>>> {
>>>>     if (H(x, x))
>>>>       HERE: goto HERE;
>>>> }
>>>>
>>>> int main()
>>>> {
>>>>     Output("Input_Halts = ", H((u32)P, (u32)P));
>>>> }
>>>>
>>>> The self-contradiction of the halting problem counter-examples is
>>>> apparently modeled after the liar paradox.
>>>
>>> P(P) (like all computations) either halts or it does not.  You tell us
>>> it halts.  You also tell up that H(P,P) == 0.  H(P,P) == 0 is the wrong
>>> answer for a halting computation.
>>
>> int main() { P(P); } specifies infinite recursion that it aborted at
>> its third function call.
> 
> P(P) halts (according to you).  H(P,P) == 0 (according to you).  That is
> wrong (according to everyone but you).
> 

void P(u32 x)
{
   if (H(x, x))
     HERE: goto HERE;
}

int main()
{
   P((u32)P);
}

The fact is that the above computation never ever halts unless some H 
aborts some P thus proving beyond all possible doubt that H[0] does 
correctly decide that P[2] (zero based addressing) never halts.

When a computation only stops running because its simulation was aborted 
this counts as a computation that never halts.

That you simply don't know the x86 language well enough to see that the 
input to H has no possible escape from its infinite recursion does not 
count as any sort of rebuttal at all.

>>>> I continue to hope against hope that you simply misunderstand this and
>>>> will eventually agree that I am correct.
>>> I merely don't like your analogy.
>>
>> Bullshit. You know that Daryl McCullough's analogy proves that I am
>> right and you only want to prove me wrong even if you have to lie to
>> make gullible fools believe that your rebuttal is valid.
> 
> Don't be silly.  You are wrong based on simple facts that you don't
> dispute.  None of the facts are in dispute:
> 
> For H to be a halt decider, H(P,I) must be true if and only of P(I)
> halts.  P(P) halts.  H(P,P) is false.
> 
> Three facts.  It's that simple.
> 



-- 
Copyright 2021 Pete Olcott

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

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

Page 1 of 4  [1] 2 3 4  Next page →

Back to top | Article view | comp.theory

csiph-web