Re: Primitive recursive vs recursive at the base of the arithmetical hierarchy.

From: Mike Oliver (mike_lists_at_verizon.net)
Date: 10/09/04

  • Next message: Farhang Farid: "AVL to Red-Black Tree" 
    Date: Fri, 08 Oct 2004 21:48:18 -0500

    H. Enderton wrote:
    > Rex Butler <RexButler@hotmail.com> wrote:
    >
    >>With regards to the theory of computability, I've noticed two
    >>alternate definitions for the base class of the arithmetical
    >>hierarchy. One defines the base class Delta_0 as the set of
    >>*primitive recursive* relations,
    >
    >
    > I can't see why anyone would do that. The class of primitive
    > recursive relations is not a particularly natural class.

    Well, it's the set of all relations definable over
    <N,0,1,+,*> using only bounded quantifiers, isn't it?
    That seems like a pretty natural thing to call Delta_0.

    >>and the other defines the base class
    >>Delta_0 as the set of (total) *recursive* relations.
    >
    >
    > Good choice. Perfectly natural. As you pointed out, we get
    > the same class for Sigma_1 in both cases.

    But then you get Delta_1 == Delta_0 -- why would you
    want that?

  • Next message: Farhang Farid: "AVL to Red-Black Tree"

    Relevant Pages