Re: on "infinitely recursive" and "recursive"

From	André G. Isaak <agisaak@gm.invalid>
Newsgroups	comp.theory
Subject	Re: on "infinitely recursive" and "recursive"
Date	2022-05-01 11:30 -0600
Organization	Christians and Atheists United Against Creeping Agnosticism
Message-ID	<t4mg34$3n9$1@dont-email.me> (permalink)
References	<20220501133707.00002134@reddwarf.jmc> <n8zbK.4460$81g4.3413@fx37.iad>

Show all headers | View raw

On 2022-05-01 11:08, Richard Damon wrote:
> On 5/1/22 8:37 AM, Mr Flibble wrote:
>> Recursive definitions are fine, infinitely recursive definitions (such
>> as The Halting Problem) are INVALID.
>>
>> RECURSIVE and INFINITELY RECURSIVE are TWO DIFFERENT THINGS.
>>
>> /Flibble
>>
> 
> And the Halting Problem isn't recursive at all, so it can't be infinity 
> recursive. NOTHING in the definition refers to itself.
> 
> The counter example is, in a way, "recursive", but that recursion can 
> only become infinite if the proposed Halt Decider turns out to fail to 
> be a Halt Decider.

Actually, even the counterexample is not recursive. It only becomes 
recursive (or recursive-like) if one assumes that H bases its answer on 
the simulation of its input. And the proof certainly does not require 
that to be the case.

André

-- 
To email remove 'invalid' & replace 'gm' with well known Google mail 
service.

Thread

on "infinitely recursive" and "recursive" Mr Flibble <flibble@reddwarf.jmc> - 2022-05-01 13:37 +0100
  Re: on "infinitely recursive" and "recursive" Ben <ben.usenet@bsb.me.uk> - 2022-05-01 15:39 +0100
    Re: on "infinitely recursive" and "recursive" polcott <polcott2@gmail.com> - 2022-05-01 11:05 -0500
      Re: on "infinitely recursive" and "recursive" Richard Damon <Richard@Damon-Family.org> - 2022-05-01 13:14 -0400
      Re: on "infinitely recursive" and "recursive" Ben <ben.usenet@bsb.me.uk> - 2022-05-02 00:50 +0100
    Re: on "infinitely recursive" and "recursive" Mr Flibble <flibble@reddwarf.jmc> - 2022-05-01 17:17 +0100
      Re: on "infinitely recursive" and "recursive" Ben <ben.usenet@bsb.me.uk> - 2022-05-02 00:44 +0100
        Re: on "infinitely recursive" and "recursive" Mr Flibble <flibble@reddwarf.jmc> - 2022-05-02 01:26 +0100
          Re: on "infinitely recursive" and "recursive" André G. Isaak <agisaak@gm.invalid> - 2022-05-01 18:29 -0600
            Re: on "infinitely recursive" and "recursive" Mr Flibble <flibble@reddwarf.jmc> - 2022-05-02 01:31 +0100
          Re: on "infinitely recursive" and "recursive" Ben <ben.usenet@bsb.me.uk> - 2022-05-02 01:49 +0100
  Re: on "infinitely recursive" and "recursive" Richard Damon <Richard@Damon-Family.org> - 2022-05-01 13:08 -0400
    Re: on "infinitely recursive" and "recursive" olcott <polcott2@gmail.com> - 2022-05-01 12:23 -0500
      Re: on "infinitely recursive" and "recursive" Richard Damon <Richard@Damon-Family.org> - 2022-05-01 14:04 -0400
    Re: on "infinitely recursive" and "recursive" André G. Isaak <agisaak@gm.invalid> - 2022-05-01 11:30 -0600
      Re: on "infinitely recursive" and "recursive" Richard Damon <Richard@Damon-Family.org> - 2022-05-01 14:10 -0400
      Re: on "infinitely recursive" and "recursive" olcott <NoOne@NoWhere.com> - 2022-05-01 13:33 -0500
        Re: on "infinitely recursive" and "recursive" André G. Isaak <agisaak@gm.invalid> - 2022-05-01 12:43 -0600
          Re: on "infinitely recursive" and "recursive" olcott <NoOne@NoWhere.com> - 2022-05-01 14:05 -0500
            Re: on "infinitely recursive" and "recursive" André G. Isaak <agisaak@gm.invalid> - 2022-05-01 13:19 -0600
              Re: on "infinitely recursive" and "recursive" olcott <NoOne@NoWhere.com> - 2022-05-01 14:24 -0500
                Re: on "infinitely recursive" and "recursive" André G. Isaak <agisaak@gm.invalid> - 2022-05-01 13:35 -0600
                Re: on "infinitely recursive" and "recursive" olcott <NoOne@NoWhere.com> - 2022-05-01 14:43 -0500
                Re: on "infinitely recursive" and "recursive" André G. Isaak <agisaak@gm.invalid> - 2022-05-01 13:45 -0600
                Re: on "infinitely recursive" and "recursive" olcott <NoOne@NoWhere.com> - 2022-05-01 14:56 -0500
                Re: on "infinitely recursive" and "recursive" Richard Damon <Richard@Damon-Family.org> - 2022-05-01 15:49 -0400
                Re: on "infinitely recursive" and "recursive" Richard Damon <Richard@Damon-Family.org> - 2022-05-01 15:43 -0400
            Re: on "infinitely recursive" and "recursive" Malcolm McLean <malcolm.arthur.mclean@gmail.com> - 2022-05-01 12:21 -0700
              Re: on "infinitely recursive" and "recursive" olcott <NoOne@NoWhere.com> - 2022-05-01 14:27 -0500
                Re: on "infinitely recursive" and "recursive" Richard Damon <Richard@Damon-Family.org> - 2022-05-01 15:52 -0400
              Re: on "infinitely recursive" and "recursive" Keith Thompson <Keith.S.Thompson+u@gmail.com> - 2022-05-01 14:10 -0700
                Re: on "infinitely recursive" and "recursive" Malcolm McLean <malcolm.arthur.mclean@gmail.com> - 2022-05-02 02:53 -0700
                Re: on "infinitely recursive" and "recursive" olcott <polcott2@gmail.com> - 2022-05-02 08:31 -0500
                Re: on "infinitely recursive" and "recursive" Ben <ben.usenet@bsb.me.uk> - 2022-05-02 15:46 +0100
                Re: on "infinitely recursive" and "recursive" Richard Damon <Richard@Damon-Family.org> - 2022-05-02 18:43 -0400
            Re: on "infinitely recursive" and "recursive" Richard Damon <Richard@Damon-Family.org> - 2022-05-01 15:27 -0400
        Re: on "infinitely recursive" and "recursive" Richard Damon <Richard@Damon-Family.org> - 2022-05-01 15:13 -0400

csiph-web