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

Groups > comp.theory > #49683

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

Show all headers | View raw

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

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