Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]
Groups > comp.lang.c > #161824
| From | Mr Flibble <flibble@reddwarf.jmc> |
|---|---|
| Newsgroups | comp.theory, comp.ai.philosophy, comp.software-eng, comp.lang.c |
| Subject | Re: How do we know that H(P,P)==0 is correct? (V4) [ strachey example ] |
| Message-ID | <20210710161537.00002347@reddwarf.jmc> (permalink) |
| References | (17 earlier) <nIGdnZEeKNGQIXX9nZ2dnUU7-f2dnZ2d@giganews.com> <20210710124050.00006bad@reddwarf.jmc> <FfSdnXqwdMIPO3T9nZ2dnUU7-XnNnZ2d@giganews.com> <20210710153034.0000569f@reddwarf.jmc> <z5WdnVkIYuC5K3T9nZ2dnUU7-QvNnZ2d@giganews.com> |
| Organization | Jupiter Mining Corp |
| Date | 2021-07-10 16:15 +0100 |
Cross-posted to 4 groups.
On Sat, 10 Jul 2021 10:00:51 -0500
olcott <NoOne@NoWhere.com> wrote:
> On 7/10/2021 9:30 AM, Mr Flibble wrote:
> > On Sat, 10 Jul 2021 08:54:23 -0500
> > olcott <NoOne@NoWhere.com> wrote:
> >
> >> On 7/10/2021 6:40 AM, Mr Flibble wrote:
> >>> On Fri, 9 Jul 2021 16:13:48 -0500
> >>> olcott <NoOne@NoWhere.com> wrote:
> >>>
> >>>> On 7/9/2021 4:08 PM, Mr Flibble wrote:
> >>>>> On Fri, 9 Jul 2021 14:24:33 -0500
> >>>>> olcott <NoOne@NoWhere.com> wrote:
> >>>>>
> >>>>>> On 7/9/2021 2:16 PM, Mr Flibble wrote:
> >>>>>>> On Fri, 9 Jul 2021 12:47:12 -0500
> >>>>>>> olcott <NoOne@NoWhere.com> wrote:
> >>>>>>>
> >>>>>>>> On 7/9/2021 12:06 PM, Mr Flibble wrote:
> >>>>>>>>> On Fri, 9 Jul 2021 08:59:51 -0500
> >>>>>>>>> olcott <NoOne@NoWhere.com> wrote:
> >>>>>>>>>> [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.
> >>>>>>>>>>
> >>>>>>>>>> No we cannot. In order to remove the pathological feedback
> >>>>>>>>>> loop such that P does the opposite of whatever H decides H
> >>>>>>>>>> simply acts as a pure simulator of P thus having no effect
> >>>>>>>>>> what-so-ever on the behavior of P until after its halt
> >>>>>>>>>> status decision has been made.
> >>>>>>>>>
> >>>>>>>>> Except your decider can only handle trivial uninteresting
> >>>>>>>>> cases: if you wish to make progress on this then prove your
> >>>>>>>>> decider works with a non-trivial case which includes
> >>>>>>>>> branching logic predicated on arbitrary program input that
> >>>>>>>>> is unknown a priori to the simulation starting; but before
> >>>>>>>>> you even do that prove your decider works with a
> >>>>>>>>> non-trivial case with branching logic predicated on
> >>>>>>>>> arbitrary program input that *is* known a priori.
> >>>>>>>>
> >>>>>>>> You continue to prove to everyone that actually knows these
> >>>>>>>> things that you are an ignoramus on this subject.
> >>>>>>>>
> >>>>>>>> That H correctly decides that all of the standard
> >>>>>>>> counter-examples templates never halt eliminates the entire
> >>>>>>>> basis of all of the conventional halting problem
> >>>>>>>> undecidability proofs.
> >>>>>>>>> I also note that you repeatedly refuse to address my point
> >>>>>>>>> regarding how x86 mov instructions can read/write from/to
> >>>>>>>>> memory mapped I/O rather than RAM so the result of the mov
> >>>>>>>>> instruction cannot be known a priori. The halting program
> >>>>>>>>> concerns computing devices and a computing device which
> >>>>>>>>> cannot do I/O is next to useless, much like your decider
> >>>>>>>>> (until you actually prove otherwise which I have a feeling
> >>>>>>>>> is never going to happen as you appear to be stuck in a
> >>>>>>>>> loop).
> >>>>>>>>>
> >>>>>>>>> /Flibble
> >>>>>>>>>
> >>>>>>>>
> >>>>>>>>
> >>>>>>>
> >>>>>>> I continue to note that you repeatedly refuse to address my
> >>>>>>> point regarding how x86 mov instructions can read/write
> >>>>>>> from/to memory mapped I/O rather than RAM so the result of
> >>>>>>> the mov instruction cannot be known a priori. The halting
> >>>>>>> program concerns computing devices and a computing device
> >>>>>>> which cannot do I/O is next to useless, much like your
> >>>>>>> decider (until you actually prove otherwise which I have a
> >>>>>>> feeling is never going to happen as you appear to be stuck in
> >>>>>>> a loop).
> >>>>>>>
> >>>>>>> /Flibble
> >>>>>>>
> >>>>>>
> >>>>>> You are the only one that believes that your points have any
> >>>>>> relevance. That you believe that data movement instructions
> >>>>>> have anything to do with control flow proves that your points
> >>>>>> have no relevance.
> >>>>>
> >>>>> You literally have no clue about what you are talking about,
> >>>>> whatsoever. This explains everything.
> >>>>>
> >>>>> /Flibble
> >>>>>
> >>>>
> >>>> *Make sure that you read all of this especially the last line*
> >>>>
> >>>> halt (p, i)
> >>>> {
> >>>> if ( program p halts on input i )
> >>>> return true ; // p halts
> >>>> else
> >>>> return false ; // p doesn’t halt
> >>>> }
> >>>> Fig. 1. Pseudocode of the Halting Function
> >>>>
> >>>> Strachey’s Impossible Program Strachey proposed a program
> >>>> based on the result of an assumed halting function [2].
> >>>> The way Strachey’s construction and other similar constructions
> >>>> are used to show the impossibility of a decideable halting
> >>>> function is quite similar to Turing’s original disproof.
> >>>> But the relevant difference we want to emphasize is that
> >>>> they do not explicitly assume an infinite number of possible
> >>>> machines (programs) or input data, because they directly use
> >>>> reductio ad absurdum to prove that both, Strachey’s construction
> >>>> and the universal halting function cannot exist.
> >>>>
> >>>> strachey ( p )
> >>>> {
> >>>> if ( halt (p, p) == true )
> >>>> L1 : goto L1 ; // loop forever
> >>>> else
> >>>> return;
> >>>> }
> >>>>
> >>>> Fig. 2. Strachey’s Impossible Program
> >>>>
> >>>> The impossibility of Strachey’s construction given in Figure 2
> >>>> becomes obvious if one tries to apply the halting function as
> >>>> follows:
> >>>>
> >>>> halt(strachey, strachey)
> >>>>
> >>>> Since in this case strachey() itself calls halt(strachey,
> >>>> strachey), it is required that the direct call of halt() and the
> >>>> nested call provide the same result. However, this leads to a
> >>>> contradiction, whatever result halt() returns. Within this
> >>>> disproof there seems to be no indication why not it could be even
> >>>> applied to finite-state systems having a concrete upper bound of
> >>>> state space.
> >>>>
> >>>> https://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.206.1468&rep=rep1&type=pdf
> >>>>
> >>>
> >>> Except your decider can only handle trivial uninteresting cases:
> >>> if you
> >>
> >> Ask other people here if being able to correctly decide the
> >> strachey case is trivial or uninteresting. Ben might be the best
> >> one to ask about this.
> >>
> >> Here is his original 1965 letter.
> >> https://academic.oup.com/comjnl/article/7/4/313/354243
> >
> > All Strachey's letter shows is that a decider cannot be part of
> > that which is being decided.
> >
> > /Flibble
> >
>
>
> // Simplified Linz Ĥ (Linz:1990:319)
> void P(u32 x)
> {
> u32 Input_Halts = H(x, x);
> if (Input_Halts)
> HERE: goto HERE;
> }
>
> int main()
> {
> u32 Input_Halts = H((u32)P, (u32)P);
> Output("Input_Halts = ", Input_Halts);
> }
>
> What it shows is that the halting problem proof can be enormously
> simplified to the impossibility of the H(P,P) in main() returning a
> correct halt status value to main().
>
> *Here are Strachey's (verbatim) own words*
> Suppose T[R] is a Boolean function taking a routine
> (or program) R with no formal or free variables as its
> argument and that for all R, T[R] — True if R terminates
> if run and that T[R] = False if R does not terminate.
> Consider the routine P defined as follows
>
> rec routine P
> §L:if T[P] go to L
> Return §
>
> If T[P] = True the routine P will loop, and it will
> only terminate if T[P] = False. In each case T[P] has
> exactly the wrong value, and this contradiction shows
> that the function T cannot exist.
>
> Strachey is the creator of CPL ancestor to BCPL then B then C
> His code above is written in his CPL programming language.
I repeat: all Strachey's letter shows is that a decider cannot be part
of that which is being decided.
/Flibble
Back to comp.lang.c | Previous | Next — Previous in thread | Next in thread | Find similar | Unroll thread
How do we know that H(P,P)==0 is correct? olcott <NoOne@NoWhere.com> - 2021-07-05 11:28 -0500
Re: How do we know that H(P,P)==0 is correct? olcott <NoOne@NoWhere.com> - 2021-07-05 14:30 -0500
Re: How do we know that H(P,P)==0 is correct? (Ben's double-talk does not work) olcott <NoOne@NoWhere.com> - 2021-07-05 16:40 -0500
Re: How do we know that H(P,P)==0 is correct? (correct halt deciding criterion measure) olcott <NoOne@NoWhere.com> - 2021-07-05 19:04 -0500
Re: How do we know that H(P,P)==0 is correct? (correct halt deciding criterion measure) olcott <NoOne@NoWhere.com> - 2021-07-05 20:01 -0500
Re: How do we know that H(P,P)==0 is correct? (correct halt deciding criterion measure) olcott <NoOne@NoWhere.com> - 2021-07-05 21:37 -0500
Re: How do we know that H(P,P)==0 is correct? (correct halt deciding criterion measure) olcott <NoOne@NoWhere.com> - 2021-07-05 22:06 -0500
Re: How do we know that H(P,P)==0 is correct? (correct halt deciding criterion measure) olcott <NoOne@NoWhere.com> - 2021-07-06 10:59 -0500
Re: How do we know that H(P,P)==0 is correct? (correct halt deciding criterion measure) olcott <NoOne@NoWhere.com> - 2021-07-06 11:33 -0500
Re: How do we know that H(P,P)==0 is correct? (V2) olcott <NoOne@NoWhere.com> - 2021-07-06 21:00 -0500
Re: How do we know that H(P,P)==0 is correct? (V3) olcott <NoOne@NoWhere.com> - 2021-07-07 11:24 -0500
Re: How do we know that H(P,P)==0 is correct? (V3) olcott <NoOne@NoWhere.com> - 2021-07-07 13:10 -0500
Re: How do we know that H(P,P)==0 is correct? (V3) olcott <NoOne@NoWhere.com> - 2021-07-07 14:51 -0500
Re: How do we know that H(P,P)==0 is correct? (V3) olcott <NoOne@NoWhere.com> - 2021-07-07 20:24 -0500
Re: How do we know that H(P,P)==0 is correct? (V3) olcott <NoOne@NoWhere.com> - 2021-07-07 21:04 -0500
Re: How do we know that H(P,P)==0 is correct? (V3) [ independent v dependent variables ] olcott <NoOne@NoWhere.com> - 2021-07-08 07:46 -0500
Re: How do we know that H(P,P)==0 is correct? (V3) [ independent v dependent variables ] olcott <NoOne@NoWhere.com> - 2021-07-08 22:54 -0500
Re: How do we know that H(P,P)==0 is correct? (V4) olcott <NoOne@NoWhere.com> - 2021-07-08 11:24 -0500
Re: How do we know that H(P,P)==0 is correct? (V4) olcott <NoOne@NoWhere.com> - 2021-07-08 20:07 -0500
Re: How do we know that H(P,P)==0 is correct? (V4) [ pathological self-reference(Olcott 2004) ] olcott <NoOne@NoWhere.com> - 2021-07-08 21:21 -0500
Re: How do we know that H(P,P)==0 is correct? (V4) [ pathological self-reference(Olcott 2004) ] olcott <NoOne@NoWhere.com> - 2021-07-08 21:36 -0500
Re: How do we know that H(P,P)==0 is correct? (V4) [ pathological self-reference(Olcott 2004) ] olcott <NoOne@NoWhere.com> - 2021-07-09 08:59 -0500
Re: How do we know that H(P,P)==0 is correct? (V4) [ pathological self-reference(Olcott 2004) ] Mr Flibble <flibble@reddwarf.jmc> - 2021-07-09 18:06 +0100
Re: How do we know that H(P,P)==0 is correct? (V4) [ pathological self-reference(Olcott 2004) ] olcott <NoOne@NoWhere.com> - 2021-07-09 12:47 -0500
Re: How do we know that H(P,P)==0 is correct? (V4) [ pathological self-reference(Olcott 2004) ] Mr Flibble <flibble@reddwarf.jmc> - 2021-07-09 20:16 +0100
Re: How do we know that H(P,P)==0 is correct? (V4) [ pathological self-reference(Olcott 2004) ] olcott <NoOne@NoWhere.com> - 2021-07-09 14:24 -0500
Re: How do we know that H(P,P)==0 is correct? (V4) [ pathological self-reference(Olcott 2004) ] Mr Flibble <flibble@reddwarf.jmc> - 2021-07-09 22:08 +0100
Re: How do we know that H(P,P)==0 is correct? (V4) [ pathological self-reference(Olcott 2004) ] olcott <NoOne@NoWhere.com> - 2021-07-09 16:13 -0500
Re: How do we know that H(P,P)==0 is correct? (V4) [ strachey example ] olcott <NoOne@NoWhere.com> - 2021-07-10 10:00 -0500
Re: How do we know that H(P,P)==0 is correct? (V4) [ strachey example ] Mr Flibble <flibble@reddwarf.jmc> - 2021-07-10 16:15 +0100
Re: How do we know that H(P,P)==0 is correct? (V4) [ strachey example ] olcott <NoOne@NoWhere.com> - 2021-07-10 10:21 -0500
Re: How do we know that H(P,P)==0 is correct? (V4) [ strachey example ] Mr Flibble <flibble@reddwarf.jmc> - 2021-07-10 16:25 +0100
Re: How do we know that H(P,P)==0 is correct? (V4) [ strachey example ] olcott <NoOne@NoWhere.com> - 2021-07-10 11:08 -0500
Re: How do we know that H(P,P)==0 is correct? (V4) [ strachey example ]( You and I ) olcott <NoOne@NoWhere.com> - 2021-07-10 11:42 -0500
Re: How do we know that H(P,P)==0 is correct? (V4) [ strachey example ] Keith Thompson <Keith.S.Thompson+u@gmail.com> - 2021-07-10 15:19 -0700
Re: How do we know that H(P,P)==0 is correct? (V4) (Ben, Kaz or Mike please talk to Flibble) olcott <NoOne@NoWhere.com> - 2021-07-10 17:24 -0500
Re: How do we know that H(P,P)==0 is correct? (V4) [ strachey example ] gazelle@shell.xmission.com (Kenny McCormack) - 2021-07-11 00:29 +0000
Re: How do we know that H(P,P)==0 is correct? (V4) [ strachey example ] olcott <NoOne@NoWhere.com> - 2021-07-10 19:57 -0500
Re: How do we know that H(P,P)==0 is correct? (V4) [ strachey example ] olcott <NoOne@NoWhere.com> - 2021-07-10 22:59 -0500
Re: How do we know that H(P,P)==0 is correct? (V4) [ pathological self-reference(Olcott 2004) ] olcott <NoOne@NoWhere.com> - 2021-07-09 17:29 -0500
Re: How do we know that H(P,P)==0 is correct? (V4) [ pathological self-reference(Olcott 2004) ] olcott <NoOne@NoWhere.com> - 2021-07-09 18:31 -0500
Re: How do we know that H(P,P)==0 is correct? (V4) [ pathological self-reference(Olcott 2004) ] olcott <NoOne@NoWhere.com> - 2021-07-09 19:33 -0500
Re: How do we know that H(P,P)==0 is correct? (V4) [ pathological self-reference(Olcott 2004) ] olcott <NoOne@NoWhere.com> - 2021-07-09 22:18 -0500
Re: How do we know that H(P,P)==0 is correct? (V4) [ pathological self-reference(Olcott 2004) ] olcott <NoOne@NoWhere.com> - 2021-07-09 23:01 -0500
Re: How do we know that H(P,P)==0 is correct? (V4) [ pathological self-reference(Olcott 2004) ] olcott <NoOne@NoWhere.com> - 2021-07-09 23:45 -0500
Re: How do we know that H(P,P)==0 is correct? (V4) [ pathological self-reference(Olcott 2004) ] olcott <NoOne@NoWhere.com> - 2021-07-10 09:25 -0500
Re: How do we know that H(P,P)==0 is correct? (V4) [ type mismatch error ] olcott <NoOne@NoWhere.com> - 2021-07-10 10:32 -0500
Re: How do we know that H(P,P)==0 is correct? (V4) [ type mismatch error ] olcott <NoOne@NoWhere.com> - 2021-07-10 11:19 -0500
Re: How do we know that H(P,P)==0 is correct? (V4) [ pathological self-reference(Olcott 2004) ] olcott <NoOne@NoWhere.com> - 2021-07-09 20:32 -0500
Re: How do we know that H(P,P)==0 is correct? (V3) olcott <NoOne@NoWhere.com> - 2021-07-07 20:31 -0500
Re: How do we know that H(P,P)==0 is correct? (V3) [ global halt decider ] olcott <NoOne@NoWhere.com> - 2021-07-08 08:29 -0500
Re: How do we know that H(P,P)==0 is correct? (V3) [ global halt decider ] olcott <NoOne@NoWhere.com> - 2021-07-09 09:02 -0500
Re: How do we know that H(P,P)==0 is correct? (Ben's double-talk does not work) olcott <NoOne@NoWhere.com> - 2021-07-05 23:15 -0500
Re: How do we know that H(P,P)==0 is correct? (Ben's double-talk does not work) olcott <NoOne@NoWhere.com> - 2021-07-06 10:26 -0500
Re: How do we know that H(P,P)==0 is correct? (Ben's double-talk does not work) Mr Flibble <flibble@reddwarf.jmc> - 2021-07-06 21:18 +0100
Re: How do we know that H(P,P)==0 is correct? (Ben's double-talk does not work) olcott <NoOne@NoWhere.com> - 2021-07-06 15:41 -0500
Re: How do we know that H(P,P)==0 is correct? (Ben's double-talk does not work) Mr Flibble <flibble@reddwarf.jmc> - 2021-07-06 23:18 +0100
Re: How do we know that H(P,P)==0 is correct? (V3) olcott <NoOne@NoWhere.com> - 2021-07-07 09:47 -0500
Re: How do we know that H(P,P)==0 is correct? (V3) olcott <NoOne@NoWhere.com> - 2021-07-07 20:15 -0500
Re: How do we know that H(P,P)==0 is correct? Bonita Montero <Bonita.Montero@gmail.com> - 2021-07-07 14:18 +0200
Re: How do we know that H(P,P)==0 is correct? Real Troll <real.troll@trolls.com> - 2021-07-07 17:25 +0000
Re: How do we know that H(P,P)==0 is correct? (V3) olcott <NoOne@NoWhere.com> - 2021-07-07 13:43 -0500
Re: How do we know that H(P,P)==0 is correct? (V3) scott@slp53.sl.home (Scott Lurndal) - 2021-07-07 19:01 +0000
Re: How do we know that H(P,P)==0 is correct? (V3) olcott <NoOne@NoWhere.com> - 2021-07-07 14:39 -0500
Re: How do we know that H(P,P)==0 is correct? Bart <bc@freeuk.com> - 2021-07-07 21:19 +0100
Re: How do we know that H(P,P)==0 is correct? olcott <NoOne@NoWhere.com> - 2021-07-07 17:05 -0500
Re: How do we know that H(P,P)==0 is correct? [ proof ] olcott <NoOne@NoWhere.com> - 2021-07-07 18:04 -0500
csiph-web