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


Groups > comp.software-eng > #2945

Re: Could H correctly decide that P never halts? [ Why can H ignore its own behavior? ](my thanks to Richard)

From Mr Flibble <flibble@reddwarf.jmc>
Newsgroups comp.theory, comp.ai.philosophy, comp.software-eng, comp.lang.c
Subject Re: Could H correctly decide that P never halts? [ Why can H ignore its own behavior? ](my thanks to Richard)
Message-ID <20210703235753.0000687f@reddwarf.jmc> (permalink)
References (4 earlier) <vN2dnQt1A5wzKH39nZ2dnUU7-LvNnZ2d@giganews.com> <k53EI.6949$Tf7.358@fx26.iad> <c-udnfvYE8oLV339nZ2dnUU7-e_NnZ2d@giganews.com> <R35EI.6950$Tf7.3601@fx26.iad> <4LqdnZ68Ev4qf339nZ2dnUU7-UHNnZ2d@giganews.com>
Organization Jupiter Mining Corp
Date 2021-07-03 23:57 +0100

Cross-posted to 4 groups.

Show all headers | View raw


On Sat, 3 Jul 2021 17:20:39 -0500
olcott <NoOne@NoWhere.com> wrote:

> On 7/3/2021 4:58 PM, Richard Damon wrote:
> > On 7/3/21 4:37 PM, olcott wrote:  
> >> On 7/3/2021 2:43 PM, Richard Damon wrote:  
> >>> On 7/3/21 3:08 PM, olcott wrote:  
> >>>> On 7/3/2021 1:17 PM, Richard Damon wrote:  
> >>>>> On 7/3/21 12:49 PM, olcott wrote:  
> >>>>>> On 7/3/2021 11:25 AM, Ben Bacarisse wrote:  
> >>>>>>> olcott <NoOne@NoWhere.com> writes:
> >>>>>>>  
> >>>>>>>>         void P(u32 x)
> >>>>>>>>         {
> >>>>>>>>           u32 Input_Halts = H(x, x);
> >>>>>>>>           if (Input_Halts)
> >>>>>>>>             HERE: goto HERE;
> >>>>>>>>         }  
> >>>>>>>
> >>>>>>> For H(P,P) to be correct one of these must apply:
> >>>>>>>
> >>>>>>>       H(P,P) == 0 and P(P) does not halt, or
> >>>>>>>       H(P,P) != 0 and P(P) halts.
> >>>>>>>
> >>>>>>> Neither is the case.
> >>>>>>>  
> >>>>>>
> >>>>>> Superficially it may seem that way until you realize (as you
> >>>>>> have already realized) that the halt criteria must be adapted
> >>>>>> for a simulating halt decider.
> >>>>>>  
> >>>>>
> >>>>> WHY? The standard definition works perfectly fine? Does P(I)
> >>>>> Halt or Not
> >>>>> when it runs.
> >>>>>  
> >>>>>> Because a simulating halt decider must always abort the
> >>>>>> simulation of every input that never halts its halt deciding
> >>>>>> criteria must be adapted.  
> >>>>>
> >>>>> But it must CORRECTLY halt. As has been shown, H incorrectly
> >>>>> aborts the simulation of P because it doesn't take into account
> >>>>> that this P WILL Halt because H does incorrectly halt its
> >>>>> simulation.  
> >>>>>>
> >>>>>> Does the input halt on its input?
> >>>>>>      must become
> >>>>>> Does the input halt without having its simulation aborted?
> >>>>>>
> >>>>>> This change is required because every input to a simulating
> >>>>>> halt decider
> >>>>>> either halts on its own or halts because its simulation has
> >>>>>> been aborted.  
> >>>>>
> >>>>> But if it halts because the contained halt decider does abort
> >>>>> its own simulation of a copy of P, then it IS a halting
> >>>>> computation. 
> >>>>
> >>>> This may be simply too difficult for you to understand.
> >>>>
> >>>> When a simulating halt decider only simulates its input until it
> >>>> detects that its input exhibits non-halting behavior then
> >>>>
> >>>> We can know that this simulating halt decider has no effect
> >>>> what-so-ever on the behavior of this input.
> >>>>  
> >>>
> >>> Right, but it DOES have an affect on its caller, which you
> >>> neglect to take into account.
> >>>  
> >>
> >> If a simulating halt decider H ALWAYS merely simulates its input
> >> until it detects that its input matches an infinite execution
> >> behavior pattern then H can always ignore its own behavior when it
> >> is analyzing the halt status of its input.  
> > 
> > No it can't. Because the fact that H does abort it simulation does
> > affect the code that we simulated CALLING that H.
> >   
> 
> No H ever aborts any P until after some P have proved beyond all 
> possible doubt that it will never halt unless aborted. Until some P
> does prove this every H only acts as an x86 emulator and nothing more.

But you can only decide it will never halt for uninteresting trivial
cases: until you decider can handle an arbitrary algorithm predicated
on arbitrary program input you've got nothing.

/Flibble

Back to comp.software-eng | Previous | Next — Previous in thread | Next in thread | Find similar | Unroll thread


Thread

Re: Could H correctly decide that P never halts? olcott <NoOne@NoWhere.com> - 2021-07-03 11:49 -0500
  Re: Could H correctly decide that P never halts? [ Why can H ignore its own behavior? ] olcott <NoOne@NoWhere.com> - 2021-07-03 14:08 -0500
    Re: Could H correctly decide that P never halts? [ Why can H ignore its own behavior? ](my thanks to Richard) olcott <NoOne@NoWhere.com> - 2021-07-03 15:37 -0500
      Re: Could H correctly decide that P never halts? [ Why can H ignore its own behavior? ](my thanks to Richard) olcott <NoOne@NoWhere.com> - 2021-07-03 17:20 -0500
        Re: Could H correctly decide that P never halts? [ Why can H ignore its own behavior? ](my thanks to Richard) Mr Flibble <flibble@reddwarf.jmc> - 2021-07-03 23:57 +0100
          Re: Could H correctly decide that P never halts? [ Why can H ignore its own behavior? ](my thanks to Richard) olcott <NoOne@NoWhere.com> - 2021-07-03 18:13 -0500
        Re: Could H correctly decide that P never halts? [ prerequisites to understanding me] olcott <NoOne@NoWhere.com> - 2021-07-03 18:34 -0500
          Re: Could H correctly decide that P never halts? [ prerequisites to understanding me] olcott <NoOne@NoWhere.com> - 2021-07-03 19:26 -0500
            Re: Could H correctly decide that P never halts? [ prerequisites to understanding me] olcott <NoOne@NoWhere.com> - 2021-07-03 21:22 -0500
              Re: Could H correctly decide that P never halts? [ prerequisites to understanding me] olcott <NoOne@NoWhere.com> - 2021-07-03 22:32 -0500
                Re: Could H correctly decide that P never halts? [ prerequisites to understanding me] olcott <NoOne@NoWhere.com> - 2021-07-04 09:24 -0500
      Re: Could H correctly decide that P never halts? [ Why can H ignore its own behavior? ](my thanks to Richard) olcott <NoOne@NoWhere.com> - 2021-07-04 09:15 -0500
        Re: Could H correctly decide that P never halts? [ Why can H ignore its own behavior? ](my thanks to Richard) olcott <NoOne@NoWhere.com> - 2021-07-04 15:09 -0500
          Re: Could H correctly decide that P never halts? [ Why can H ignore its own behavior? ](my thanks to Richard) olcott <NoOne@NoWhere.com> - 2021-07-04 20:42 -0500
            Re: Could H correctly decide that P never halts? [ Why can H ignore its own behavior? ](my thanks to Richard) olcott <NoOne@NoWhere.com> - 2021-07-05 08:40 -0500
          Re: Could H correctly decide that P never halts? [ Why can H ignore its own behavior? ](my thanks to Richard) olcott <NoOne@NoWhere.com> - 2021-07-04 23:52 -0500
          Re: Could H correctly decide that P never halts? [ Why can H ignore its own behavior? ](my thanks to Richard) olcott <NoOne@NoWhere.com> - 2021-07-05 09:31 -0500
          Re: Could H correctly decide that P never halts? olcott <NoOne@NoWhere.com> - 2021-07-05 17:38 -0500
        Re: Could H correctly decide that P never halts? [ Why can H ignore its own behavior? ](my thanks to Richard) olcott <NoOne@NoWhere.com> - 2021-07-05 08:07 -0500
        Re: Could H correctly decide that P never halts? [ Why can H ignore its own behavior? ](my thanks to Richard) olcott <NoOne@NoWhere.com> - 2021-07-05 08:18 -0500
  Re: Could H correctly decide that P never halts? olcott <NoOne@NoWhere.com> - 2021-07-03 16:21 -0500
    Re: Could H correctly decide that P never halts? [ already agreed ] olcott <NoOne@NoWhere.com> - 2021-07-03 19:30 -0500
      Re: Could H correctly decide that P never halts? [ already agreed ] olcott <NoOne@NoWhere.com> - 2021-07-04 12:00 -0500
      Re: Could H correctly decide that P never halts? [ already agreed ] olcott <NoOne@NoWhere.com> - 2021-07-04 20:57 -0500
        Re: Could H correctly decide that P never halts? [ already agreed ] olcott <NoOne@NoWhere.com> - 2021-07-04 21:28 -0500
          Re: Could H correctly decide that P never halts? [ already agreed ] olcott <NoOne@NoWhere.com> - 2021-07-04 22:09 -0500
          Re: Could H correctly decide that P never halts? [ already agreed ] olcott <NoOne@NoWhere.com> - 2021-07-05 19:54 -0500
            Re: Could H correctly decide that P never halts? [ already agreed ] olcott <NoOne@NoWhere.com> - 2021-07-05 22:30 -0500
        Re: Could H correctly decide that P never halts? [ halting criteria ] olcott <NoOne@NoWhere.com> - 2021-07-05 08:26 -0500
        Re: Could H correctly decide that P never halts? [ Richard's excellent summation ] olcott <NoOne@NoWhere.com> - 2021-07-05 19:12 -0500

csiph-web