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

Groups > comp.theory > #49685

Re: On recursion and infinite recursion (reprise #2)

Show all headers | View raw

On Wed, 4 May 2022 20:21:04 -0400
Richard Damon <Richard@Damon-Family.org> wrote:

> On 5/4/22 8:05 PM, Mr Flibble wrote:
> > On Wed, 4 May 2022 20:02:57 -0400
> > Richard Damon <Richard@Damon-Family.org> wrote:
> >   
> >> On 5/4/22 7:51 PM, Mr Flibble wrote:  
> >>> On Wed, 4 May 2022 19:42:19 -0400
> >>> Richard Damon <Richard@Damon-Family.org> wrote:
> >>>      
> >>>> On 5/4/22 12:46 PM, Mr Flibble wrote:  
> >>>>> The halting problem theorem and proof thereof [Turing, 1937]
> >>>>> (upon which other currently extant halting problem proofs are
> >>>>> derived) is invalid due to an invalid "impossible program"
> >>>>> [Strachey, 1965] that arises not from a function call-like
> >>>>> infinite recursion but from a category error in the form of an
> >>>>> invalid (erroneous) infinite recursion present in the proof
> >>>>> [Wikipedia, 2022].
> >>>>>
> >>>>> The categories involved in the category error are the decider
> >>>>> and that which is being decided.  Currently extant attempts to
> >>>>> conflate the decider with that which is being decided are
> >>>>> infinitely recursive and thus invalid.
> >>>>>
> >>>>> /Flibble
> >>>>>         
> >>>>
> >>>> And what is the error between the decider and the decided.
> >>>>
> >>>> The Decider is H.
> >>>>
> >>>> The thing to be decideer is H^ applied to <H^>
> >>>>
> >>>> Now, if you want to claim that H^ can't use H, then you are
> >>>> saying either that Turing Macines aren't allowed to use other
> >>>> Turing Machines, which is crasy, or that H just can't be asked
> >>>> about machines which are based on it, at which point that is just
> >>>> admitting that the Halting Problem is in fact impossible, as
> >>>> there exist some VALID programs (which H^ is) that H just can't
> >>>> be asked to decide on.
> >>>>
> >>>> Note, H^ is NOT recursive in definition (unless H is). H^ is
> >>>> basically jast a "call" to H with a little bit of simple logic
> >>>> around it.
> >>>>
> >>>> The "recursion" (which isn't actually recursion) comes about
> >>>> because we give H^ and input that just happens to be a
> >>>> representation of itself, and H^ doesn't actually know that.
> >>>>
> >>>> If H actually meets the requirements of being a decider (and thus
> >>>> also of being a Comptation), then we get no infinite "recursion",
> >>>> as the H inside H^ will, by necessity, return an answer after
> >>>> finite time, and H^ will either Halt or go into a simple infinite
> >>>> loop.
> >>>>
> >>>> H is thus just proved to give the wrong answer.
> >>>>
> >>>> If H refuses to give the wrong answer, then it turns out to not
> >>>> be a decider and just loops forever with an ever growing tape as
> >>>> the level of simulation just keeps increasing.
> >>>>
> >>>> Note, we NEVER get back to H^.q0 or any of the states of H^ up to
> >>>> H^.qx, as the entire execution trace is within its copy of H
> >>>> doing its simulation to try to decide. There is no actual
> >>>> Recursion.
> >>>>
> >>>>
> >>>> Yes, in trying to decide how we might program H to try to get the
> >>>> right answer, we can think about levels of recursion, but those
> >>>> are not actually in the real trace of the execution of H^. Once
> >>>> we actual make a decision on how we are going to attempt to make
> >>>> an H, and establish a fixed algorithm to program into H, we find
> >>>> that we have failed to make a correct decider, because, as the
> >>>> theorem says, it IS impossible. This doesn't mean the problem is
> >>>> "invalid" just impossible.
> >>>>
> >>>> Just like the problem of creating a program to always win at Tic
> >>>> Tac Toe. The problem is well defined, just impossible due to the
> >>>> nature of the game.  
> >>>
> >>> Nope. The infinite recursion is a category error and therefore
> >>> invalid: you and the rest of you shower appear to have a blindspot
> >>> to this fact.
> >>>
> >>> /Flibble
> >>>      
> >>
> >> And what is the infinite recursion in the HALTING PROBLEM?
> >>
> >> There is none.  
> > 
> > I know, which is why I explicitly said halting problem THEOREM in
> > this post.
> >   
> >>
> >> Or in the Theorem, (That there doesn't exist an answer to the
> >> Halting Problem), THERE IS NONE.  
> > 
> > The invalid infinite recursion is in the THEOREM as stated in
> > [Wikipedia, 2022].
> >   
> >>
> >> In fact, you could say that "infinite recursion" is one of the
> >> things that can be used to PROVE the Theorem, as any answer (by
> >> simulation) to the problem would need to invoke an infinte
> >> recursion to answer it. Thus the ANSWER (which is what is trying
> >> to do the infinite recursion) and not the problem (which has no
> >> recursion) is invalid.  
> > 
> > However the infinite recursion is a category error in this case so
> > cannot prove anything.
> > 
> > /Flibble
> >   
> 
> But what HAS the infinite recursion?
> 
> Not the PROBLEM.
> 
> Not the Theorem.
> 
> Not H^
> 
> The only thing that comes close is H, so that means that the H
> doesn't exist, and thus the Problem is intact and the Theorem proved.

[Strachey, 1965] simplifies the theorem making the infinite recursion
obvious; see also [Wikipedia, 2022].

/Flibble

Back to comp.theory | Previous | Next — Previous in thread | Next in thread | Find similar | Unroll thread

Thread

On recursion and infinite recursion (reprise #2) Mr Flibble <flibble@reddwarf.jmc> - 2022-05-04 17:46 +0100
  Re: On recursion and infinite recursion (reprise #2) André G. Isaak <agisaak@gm.invalid> - 2022-05-04 10:53 -0600
    Re: On recursion and infinite recursion (reprise #2) Mr Flibble <flibble@reddwarf.jmc> - 2022-05-04 17:56 +0100
      Re: On recursion and infinite recursion (reprise #2) olcott <polcott2@gmail.com> - 2022-05-04 12:53 -0500
        Re: On recursion and infinite recursion (reprise #2) Mr Flibble <flibble@reddwarf.jmc> - 2022-05-04 19:00 +0100
    Re: On recursion and infinite recursion (reprise #2) olcott <polcott2@gmail.com> - 2022-05-04 12:52 -0500
  Re: On recursion and infinite recursion (reprise #2) olcott <polcott2@gmail.com> - 2022-05-04 12:51 -0500
  Re: On recursion and infinite recursion (reprise #2) Richard Damon <Richard@Damon-Family.org> - 2022-05-04 19:42 -0400
    Re: On recursion and infinite recursion (reprise #2) Mr Flibble <flibble@reddwarf.jmc> - 2022-05-05 00:51 +0100
      Re: On recursion and infinite recursion (reprise #2) Python <python@example.invalid> - 2022-05-05 01:58 +0200
      Re: On recursion and infinite recursion (reprise #2) Richard Damon <Richard@Damon-Family.org> - 2022-05-04 20:02 -0400
        Re: On recursion and infinite recursion (reprise #2) Mr Flibble <flibble@reddwarf.jmc> - 2022-05-05 01:05 +0100
          Re: On recursion and infinite recursion (reprise #2) Richard Damon <Richard@Damon-Family.org> - 2022-05-04 20:21 -0400
            Re: On recursion and infinite recursion (reprise #2) Mr Flibble <flibble@reddwarf.jmc> - 2022-05-05 01:24 +0100
              Re: On recursion and infinite recursion (reprise #2) Richard Damon <Richard@Damon-Family.org> - 2022-05-04 20:41 -0400
                Re: On recursion and infinite recursion (reprise #2) Mr Flibble <flibble@reddwarf.jmc> - 2022-05-05 17:47 +0100
                Re: On recursion and infinite recursion (reprise #2) olcott <polcott2@gmail.com> - 2022-05-05 16:40 -0500
                Re: On recursion and infinite recursion (reprise #2) Richard Damon <Richard@Damon-Family.org> - 2022-05-05 22:28 -0400

csiph-web