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

Groups > comp.theory > #49383 > unrolled thread

on "infinitely recursive" and "recursive"

Back to article view | Back to comp.theory

Contents

  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

Page 1 of 2  [1] 2  Next page →

#49383 — on "infinitely recursive" and "recursive"

Recursive definitions are fine, infinitely recursive definitions (such
as The Halting Problem) are INVALID.

RECURSIVE and INFINITELY RECURSIVE are TWO DIFFERENT THINGS.

/Flibble

[toc] | [next] | [standalone]

#49390

Mr Flibble <flibble@reddwarf.jmc> writes:

> Recursive definitions are fine, infinitely recursive definitions (such
> as The Halting Problem) are INVALID.

(1) The halting problem is not an infinitely recursive definition.

(2) Infinitely recursive definitions are often fine.  For example, the
list of Fibonacci numbers:

  fibs = 1 : 1 : zipWith (+) fibs (tail fibs)

or the list of factorials:

   facts = prod 1 1 where prod p n = p : prod (p*n) (n+1)

-- 
Ben.

[toc] | [prev] | [next] | [standalone]

#49395

On 5/1/2022 9:39 AM, Ben wrote:
> Mr Flibble <flibble@reddwarf.jmc> writes:
> 
>> Recursive definitions are fine, infinitely recursive definitions (such
>> as The Halting Problem) are INVALID.
> 
> (1) The halting problem is not an infinitely recursive definition.
> 
> (2) Infinitely recursive definitions are often fine.  For example, the
> list of Fibonacci numbers:
> 

This type is never fine: // Adapted from Clocksin & Mellish
foo(foo(foo(foo(foo(foo(foo(foo(foo(foo(foo(foo(...))))))))))))

Because Gödel says
14 Every epistemological antinomy can likewise be used for a similar 
undecidability proof

G ↔ ¬Provable(F, G) is an epistemological antinomy therefore it is 
necessarily sufficiently equivalent to his G.

Likewise with this one: LP ↔ ¬True(LP)
It can be evaluated as semantically incorrect without the need to define 
True(). No matter how True() is defined LP ↔ ¬True(LP) is semantically 
incorrect because it specifies this:

LP ↔ ¬True(¬True(¬True(¬True(¬True(¬True(¬True(¬True(LP))))))))
and Prolog can detect and reject this with unify_with_occurs_check.


>    fibs = 1 : 1 : zipWith (+) fibs (tail fibs)
> 
> or the list of factorials:
> 
>     facts = prod 1 1 where prod p n = p : prod (p*n) (n+1)
> 


-- 
Copyright 2022 Pete Olcott "Talent hits a target no one else can hit;
Genius hits a target no one else can see." Arthur Schopenhauer

[toc] | [prev] | [next] | [standalone]

#49406

On 5/1/22 12:05 PM, polcott wrote:
> On 5/1/2022 9:39 AM, Ben wrote:
>> Mr Flibble <flibble@reddwarf.jmc> writes:
>>
>>> Recursive definitions are fine, infinitely recursive definitions (such
>>> as The Halting Problem) are INVALID.
>>
>> (1) The halting problem is not an infinitely recursive definition.
>>
>> (2) Infinitely recursive definitions are often fine.  For example, the
>> list of Fibonacci numbers:
>>
> 
> This type is never fine: // Adapted from Clocksin & Mellish
> foo(foo(foo(foo(foo(foo(foo(foo(foo(foo(foo(foo(...))))))))))))

Depends on the definition of foo.

If foo is the function "fact" I have presented, then the unwinding 
becomes exactly that to a too dumb naive expansion.

Thus "never" is incorrect.


> 
> Because Gödel says
> 14 Every epistemological antinomy can likewise be used for a similar 
> undecidability proof
> 
> G ↔ ¬Provable(F, G) is an epistemological antinomy therefore it is 
> necessarily sufficiently equivalent to his G.
> 
> Likewise with this one: LP ↔ ¬True(LP)
> It can be evaluated as semantically incorrect without the need to define 
> True(). No matter how True() is defined LP ↔ ¬True(LP) is semantically 
> incorrect because it specifies this:
> 
> LP ↔ ¬True(¬True(¬True(¬True(¬True(¬True(¬True(¬True(LP))))))))
> and Prolog can detect and reject this with unify_with_occurs_check.


Because Prolog is too limited to be able to fully handle this sort of 
recursion. Prolog apparently can't handle the recursive definition of 
fact(n), which just proves that its rejection of something as 
"infinitely recursive" is NOT "Proof" that it is invalid.

> 
> 
>>    fibs = 1 : 1 : zipWith (+) fibs (tail fibs)
>>
>> or the list of factorials:
>>
>>     facts = prod 1 1 where prod p n = p : prod (p*n) (n+1)
>>
> 
> 

[toc] | [prev] | [next] | [standalone]

#49473

polcott <polcott2@gmail.com> writes:

> On 5/1/2022 9:39 AM, Ben wrote:
>> Mr Flibble <flibble@reddwarf.jmc> writes:
>> 
>>> Recursive definitions are fine, infinitely recursive definitions (such
>>> as The Halting Problem) are INVALID.
>> (1) The halting problem is not an infinitely recursive definition.
>> (2) Infinitely recursive definitions are often fine.  For example, the
>> list of Fibonacci numbers:
>
> This type is never fine:

So you agree that some are valid?  How are E and the specification of P
coming along?

-- 
Ben.
"le génie humain a des limites, quand la bêtise humaine n’en a pas"
Alexandre Dumas (fils)

[toc] | [prev] | [next] | [standalone]

#49398

On Sun, 01 May 2022 15:39:35 +0100
Ben <ben.usenet@bsb.me.uk> wrote:

> Mr Flibble <flibble@reddwarf.jmc> writes:
> 
> > Recursive definitions are fine, infinitely recursive definitions
> > (such as The Halting Problem) are INVALID.  
> 
> (1) The halting problem is not an infinitely recursive definition.
> 
> (2) Infinitely recursive definitions are often fine.  For example, the
> list of Fibonacci numbers:
> 
>   fibs = 1 : 1 : zipWith (+) fibs (tail fibs)

FOR FUCKS SAKE, HOW STUPID ARE YOU? THAT IS A RECURSIVE DEFINITION NOT
AN *INFINITELY* RECURSIVE DEFINITION AS IT TERMINATES.

/Flibble

[toc] | [prev] | [next] | [standalone]

#49472

Mr Flibble <flibble@reddwarf.jmc> writes:

> On Sun, 01 May 2022 15:39:35 +0100
> Ben <ben.usenet@bsb.me.uk> wrote:
>
>> Mr Flibble <flibble@reddwarf.jmc> writes:
>> 
>> > Recursive definitions are fine, infinitely recursive definitions
>> > (such as The Halting Problem) are INVALID.  
>> 
>> (1) The halting problem is not an infinitely recursive definition.
>> 
>> (2) Infinitely recursive definitions are often fine.  For example, the
>> list of Fibonacci numbers:
>> 
>>   fibs = 1 : 1 : zipWith (+) fibs (tail fibs)
>
> FOR FUCKS SAKE, HOW STUPID ARE YOU? THAT IS A RECURSIVE DEFINITION NOT
> AN *INFINITELY* RECURSIVE DEFINITION AS IT TERMINATES.

Look again.  What is the terminating condition?  There is none.

-- 
Ben.

[toc] | [prev] | [next] | [standalone]

#49477

On Mon, 02 May 2022 00:44:56 +0100
Ben <ben.usenet@bsb.me.uk> wrote:

> Mr Flibble <flibble@reddwarf.jmc> writes:
> 
> > On Sun, 01 May 2022 15:39:35 +0100
> > Ben <ben.usenet@bsb.me.uk> wrote:
> >  
> >> Mr Flibble <flibble@reddwarf.jmc> writes:
> >>   
> >> > Recursive definitions are fine, infinitely recursive definitions
> >> > (such as The Halting Problem) are INVALID.    
> >> 
> >> (1) The halting problem is not an infinitely recursive definition.
> >> 
> >> (2) Infinitely recursive definitions are often fine.  For example,
> >> the list of Fibonacci numbers:
> >> 
> >>   fibs = 1 : 1 : zipWith (+) fibs (tail fibs)  
> >
> > FOR FUCKS SAKE, HOW STUPID ARE YOU? THAT IS A RECURSIVE DEFINITION
> > NOT AN *INFINITELY* RECURSIVE DEFINITION AS IT TERMINATES.  
> 
> Look again.  What is the terminating condition?  There is none.
> 

It doesn't terminate because it is effectively an unbounded generator
however it will always terminate UPON USE (thunk evaluation) and this
usage is different to the infinitely recursive halting
problem definition which does not terminate.  There is no category error
here but there is a category error in the halting problem definition.

/Flibble

[toc] | [prev] | [next] | [standalone]

#49478

On 2022-05-01 18:26, Mr Flibble wrote:
> On Mon, 02 May 2022 00:44:56 +0100
> Ben <ben.usenet@bsb.me.uk> wrote:
> 
>> Mr Flibble <flibble@reddwarf.jmc> writes:
>>
>>> On Sun, 01 May 2022 15:39:35 +0100
>>> Ben <ben.usenet@bsb.me.uk> wrote:
>>>   
>>>> Mr Flibble <flibble@reddwarf.jmc> writes:
>>>>    
>>>>> Recursive definitions are fine, infinitely recursive definitions
>>>>> (such as The Halting Problem) are INVALID.
>>>>
>>>> (1) The halting problem is not an infinitely recursive definition.
>>>>
>>>> (2) Infinitely recursive definitions are often fine.  For example,
>>>> the list of Fibonacci numbers:
>>>>
>>>>    fibs = 1 : 1 : zipWith (+) fibs (tail fibs)
>>>
>>> FOR FUCKS SAKE, HOW STUPID ARE YOU? THAT IS A RECURSIVE DEFINITION
>>> NOT AN *INFINITELY* RECURSIVE DEFINITION AS IT TERMINATES.
>>
>> Look again.  What is the terminating condition?  There is none.
>>
> 
> It doesn't terminate because it is effectively an unbounded generator
> however it will always terminate UPON USE (thunk evaluation) and this

Do you actual have any familiarity with Haskell?

André


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

[toc] | [prev] | [next] | [standalone]

#49479

On Sun, 1 May 2022 18:29:50 -0600
André G. Isaak <agisaak@gm.invalid> wrote:

> On 2022-05-01 18:26, Mr Flibble wrote:
> > On Mon, 02 May 2022 00:44:56 +0100
> > Ben <ben.usenet@bsb.me.uk> wrote:
> >   
> >> Mr Flibble <flibble@reddwarf.jmc> writes:
> >>  
> >>> On Sun, 01 May 2022 15:39:35 +0100
> >>> Ben <ben.usenet@bsb.me.uk> wrote:
> >>>     
> >>>> Mr Flibble <flibble@reddwarf.jmc> writes:
> >>>>      
> >>>>> Recursive definitions are fine, infinitely recursive definitions
> >>>>> (such as The Halting Problem) are INVALID.  
> >>>>
> >>>> (1) The halting problem is not an infinitely recursive
> >>>> definition.
> >>>>
> >>>> (2) Infinitely recursive definitions are often fine.  For
> >>>> example, the list of Fibonacci numbers:
> >>>>
> >>>>    fibs = 1 : 1 : zipWith (+) fibs (tail fibs)  
> >>>
> >>> FOR FUCKS SAKE, HOW STUPID ARE YOU? THAT IS A RECURSIVE DEFINITION
> >>> NOT AN *INFINITELY* RECURSIVE DEFINITION AS IT TERMINATES.  
> >>
> >> Look again.  What is the terminating condition?  There is none.
> >>  
> > 
> > It doesn't terminate because it is effectively an unbounded
> > generator however it will always terminate UPON USE (thunk
> > evaluation) and this  
> 
> Do you actual have any familiarity with Haskell?

Not today and not tomorrow but soon.

/Flibble

[toc] | [prev] | [next] | [standalone]

#49480

Mr Flibble <flibble@reddwarf.jmc> writes:

> On Mon, 02 May 2022 00:44:56 +0100
> Ben <ben.usenet@bsb.me.uk> wrote:
>
>> Mr Flibble <flibble@reddwarf.jmc> writes:
>> 
>> > On Sun, 01 May 2022 15:39:35 +0100
>> > Ben <ben.usenet@bsb.me.uk> wrote:
>> >  
>> >> Mr Flibble <flibble@reddwarf.jmc> writes:
>> >>   
>> >> > Recursive definitions are fine, infinitely recursive definitions
>> >> > (such as The Halting Problem) are INVALID.    
>> >> 
>> >> (1) The halting problem is not an infinitely recursive definition.
>> >> 
>> >> (2) Infinitely recursive definitions are often fine.  For example,
>> >> the list of Fibonacci numbers:
>> >> 
>> >>   fibs = 1 : 1 : zipWith (+) fibs (tail fibs)  
>> >
>> > FOR FUCKS SAKE, HOW STUPID ARE YOU? THAT IS A RECURSIVE DEFINITION
>> > NOT AN *INFINITELY* RECURSIVE DEFINITION AS IT TERMINATES.  
>> 
>> Look again.  What is the terminating condition?  There is none.
>
> It doesn't terminate because it is effectively an unbounded generator
> however it will always terminate UPON USE

(1) The definition either is or it not infinitely recursive.  The use
does not alter that.

(2) Not all uses of this definition terminate.

> (thunk evaluation) and this
> usage is different to the infinitely recursive halting
> problem definition which does not terminate.

The haling problem definition is not recursive.

> There is no category error here but there is a category error in the
> halting problem definition.

There is no "category error" in the halting problem definition. 

-- 
Ben.

[toc] | [prev] | [next] | [standalone]

#49405

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.

Otherwise, it is no more infinitely recursive then the recursive 
definition of factorial.

[toc] | [prev] | [next] | [standalone]

#49411

On 5/1/2022 12:08 PM, 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.
> 

In computability theory, the halting problem is the problem of 
determining, from a description of an arbitrary computer program and an 
input, whether the program will finish running, or continue to run forever.

For any program H that might determine if programs halt, a 
"pathological" program P, called with some input, can pass its own 
source and its input to H and then specifically do the opposite of what 
H predicts P will do.

void P(u32 x)
{
   if (H(x, x))
     HERE: goto HERE;
   return;
}

https://en.wikipedia.org/wiki/Halting_problem

When H(P,P) is invoked H refers to itself embedded within P.
I have spent decades on the generic notion of pathological self-reference.

> 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.
> 
> Otherwise, it is no more infinitely recursive then the recursive 
> definition of factorial.


-- 
Copyright 2022 Pete Olcott "Talent hits a target no one else can hit;
Genius hits a target no one else can see." Arthur Schopenhauer

[toc] | [prev] | [next] | [standalone]

#49418

On 5/1/22 1:23 PM, olcott wrote:
> On 5/1/2022 12:08 PM, 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.
>>
> 
> In computability theory, the halting problem is the problem of 
> determining, from a description of an arbitrary computer program and an 
> input, whether the program will finish running, or continue to run forever.

And that ends the definition of the Halting Problem, which is NOT recursive.

> 
> For any program H that might determine if programs halt, a 
> "pathological" program P, called with some input, can pass its own 
> source and its input to H and then specifically do the opposite of what 
> H predicts P will do.
> 
> void P(u32 x)
> {
>    if (H(x, x))
>      HERE: goto HERE;
>    return;
> }
> 
> https://en.wikipedia.org/wiki/Halting_problem
> 
> When H(P,P) is invoked H refers to itself embedded within P.
> I have spent decades on the generic notion of pathological self-reference.

And yes, the counter example is recursive, but NOT infinitely so if H 
meets the requirements of being a decider.

If H doesn't meet the requirements of being a decider, and thus ALWAYS 
answering, and doesn't answer for H(P,P), then it isn't a counter 
example, as if fails to meet the requirements.

This is just like fact(n) is NOT infinitely recursive, for any finite n.


> 
>> 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.
>>
>> Otherwise, it is no more infinitely recursive then the recursive 
>> definition of factorial.
> 
> 

[toc] | [prev] | [next] | [standalone]

#49414

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.

[toc] | [prev] | [next] | [standalone]

#49419

On 5/1/22 1:30 PM, André G. Isaak wrote:
> 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é
> 

True, which is why I quoted "recursive", it is merely referential. And 
even with simulation it sort of isn't recursive, since we are supposed 
to be using different copies of the function, so the recursion is only 
on a "meta" level that knows the input is based on the decider, but not 
at the actual physical computation layer, since we are just invoking a 
long series of machines with the same descriptions, since Turing 
Machines are limited in the ways they can handle recursion, needing to 
use their tape to implement it.

[toc] | [prev] | [next] | [standalone]

#49421

On 5/1/2022 12:30 PM, André G. Isaak wrote:
> 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é
> 

Since the definition of H is wide open and can be anything at all that 
meets the spec, if any of these definitions make the "impossible" input 
decidable then this refutes the proofs.

-- 
Copyright 2022 Pete Olcott

"Talent hits a target no one else can hit;
  Genius hits a target no one else can see."
  Arthur Schopenhauer

[toc] | [prev] | [next] | [standalone]

#49423

On 2022-05-01 12:33, olcott wrote:
> On 5/1/2022 12:30 PM, André G. Isaak wrote:
>> 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é
>>
> 
> Since the definition of H is wide open and can be anything at all that 
> meets the spec, if any of these definitions make the "impossible" input 
> decidable then this refutes the proofs.

But the spec is as follows:

Hq0 <M> w ⊢* Hqy iff M applied to w halts
           ⊢* Hqn otherwise

Yours fails to meet this spec.

André

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

[toc] | [prev] | [next] | [standalone]

#49425

On 5/1/2022 1:43 PM, André G. Isaak wrote:
> On 2022-05-01 12:33, olcott wrote:
>> On 5/1/2022 12:30 PM, André G. Isaak wrote:
>>> 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é
>>>
>>
>> Since the definition of H is wide open and can be anything at all that 
>> meets the spec, if any of these definitions make the "impossible" 
>> input decidable then this refutes the proofs.
> 
> But the spec is as follows:
> 
> Hq0 <M> w ⊢* Hqy iff M applied to w halts
>            ⊢* Hqn otherwise
> 
> Yours fails to meet this spec.
> 
> André
> 

You keep insisting that H must be a mind reader and base it decision on 
something other than its input parameters when you already know that all 
deciders compute the mapping from their inputs to their own final state.

Thus you gleefully contradict facts that you accept as true. Anyone that 
contradicts facts that they know are true is a liar by definition.

-- 
Copyright 2022 Pete Olcott

"Talent hits a target no one else can hit;
  Genius hits a target no one else can see."
  Arthur Schopenhauer

[toc] | [prev] | [next] | [standalone]

#49427

On 2022-05-01 13:05, olcott wrote:
> On 5/1/2022 1:43 PM, André G. Isaak wrote:
>> On 2022-05-01 12:33, olcott wrote:
>>> On 5/1/2022 12:30 PM, André G. Isaak wrote:
>>>> 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é
>>>>
>>>
>>> Since the definition of H is wide open and can be anything at all 
>>> that meets the spec, if any of these definitions make the 
>>> "impossible" input decidable then this refutes the proofs.
>>
>> But the spec is as follows:
>>
>> Hq0 <M> w ⊢* Hqy iff M applied to w halts
>>            ⊢* Hqn otherwise
>>
>> Yours fails to meet this spec.
>>
>> André
>>
> 
> You keep insisting that H must be a mind reader and base it decision on 
> something other than its input parameters when you already know that all 
> deciders compute the mapping from their inputs to their own final state.

Even if your view that TM's can only answer about their inputs were 
true, the spec is what the spec is. Not every spec can be met.

I can specify a Turing Machine as follows (where w is some string)

Mq0 w ⊢* Mqy iff the moon is full
       ⊢* Mqn otherwise

It's not possible to write such a TM, but the fact that the spec can't 
be met doesn't entitle you to change it to something else that can be 
met. You have to simply assert that the spec cannot be met.

André

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

[toc] | [prev] | [next] | [standalone]

Page 1 of 2  [1] 2  Next page →

Back to top | Article view | comp.theory

csiph-web