XPost: comp.theory, comp.ai.philosophy, comp.software-eng   
   From: flibble@reddwarf.jmc   
      
   On Thu, 15 Jul 2021 13:04:42 -0500   
   olcott  wrote:   
      
   > On 7/15/2021 1:00 PM, Mr Flibble wrote:   
   > > On Thu, 15 Jul 2021 18:48:01 +0100   
   > > Mr Flibble  wrote:   
   > >   
   > >> On Thu, 15 Jul 2021 12:42:22 -0500   
   > >> olcott  wrote:   
   > >>   
   > >>> On 7/15/2021 12:22 PM, Mr Flibble wrote:   
   > >>>> Hi!   
   > >>>>   
   > >>>>   From Wikipedia Halting Problem page:   
   > >>>>   
   > >>>> 	For any program f that might determine if programs halt,   
   > >>>> a "pathological" program g, called with some input, can pass   
   > >>>> its own source and its input to f and then specifically do the   
   > >>>> 	opposite of what f predicts g will do. No f can exist   
   > >>>> that handles this case.   
   > >>>>   
   > >>>> To me this looks like everyone is assuming that the halting   
   > >>>> problem is undecidable based on a misunderstanding of the   
   > >>>> contradiction crystallized by [Strachen 1965].   
   > >>>>   
   > >>>> Strachen isn't saying the halting problem is undecidable, he is   
   > >>>> saying that there is a contradiction that means that a decider   
   > >>>> can not be a part of or called by that which is being decided.   
   > >>>> This doesn't mean that the halting problem is not undecidable   
   > >>>> but it does mean that if that Wikipedia extract is the current   
   > >>>> state of the art then nobody has proven that the HP is   
   > >>>> undecidable, at least for non-"pathological" programs.   
   > >>>>   
   > >>>> Olcott is on to something. :)   
   > >>>>   
   > >>>> /Flibble   
   > >>>>   
   > >>>   
   > >>> I am really glad that you are back.   
   > >>> Strachen  saying that the halting problem is undecidable.   
   > >>   
   > >> No he isn't he is saying a decider cannot decide a program that is   
   > >> aware of the decider, i.e. is "pathological". So, given two things:   
   > >>   
   > >> (1) a decider that can decide non-pathological programs, and   
   > >> (2) a decider that can detect if a program is pathological (i.e. is   
   > >> aware of the decider),   
   > >>   
   > >> then:   
   > >>   
   > >> the halting problem becomes decidable.   
   > >>   
   > >> Unless I am missing something.   
   > >   
   > > 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   
      
   --- SoupGate-Win32 v1.05   
    * Origin: you cannot sedate... all the things you hate (1:229/2)