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

Groups > comp.theory > #49678

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

Show all headers | View raw

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.

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