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

Groups > comp.theory > #49680

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

Show all headers | View raw

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

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