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

Groups > comp.theory > #49730

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

Show all headers | View raw

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

> On 5/4/22 8:24 PM, Mr Flibble wrote:
> > 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
> >   
> 
> The THEOREM is just that there exist no H that statisfies that
> Halting Problem, so that is NOT recursive at all. And has nothing to
> "Simplify"
> 
> You seem to have a category error in distinguishing between the
> Theorem, and a proof of it.
> 
> So again, WHAT has an invalid infinite recursion.
> 
> Not the PROBLEM
> 
> Not the THEOREM
> 
> Not even the H^ that proves the THEOREM.
> 
> The only thing that gets into an infinite recursion is the possible 
> answer, which by your logic is enough to prove it doesn't exist, and 
> thus the Theorem is proved.

I see that you continue to want to play word games. Oh well. You stated
in an earlier reply that paragraph 2 of [Wikipedia, 2022) was a summary
of the proof and this does indeed contain the erroneous infinite
recursion, erroneous due to a category error.  I will make another
post (reprise #3) for your benefit.

/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