Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]
Groups > comp.software-eng > #2945
| 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.
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
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