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

Groups > comp.theory > #49682

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

Show all headers | View raw

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.

Or in the Theorem, (That there doesn't exist an answer to the Halting 
Problem), THERE IS NONE.

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.

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