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

From: H. Enderton (hbe_at_sonia.math.ucla.edu)
Date: 10/08/04 

Date: Fri, 8 Oct 2004 17:13:31 +0000 (UTC)

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.

>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.

>BTW, what are the recommended texts on the theory of computability?

Cutland's book is still a good one.

--Herb Enderton

Relevant Pages

  • Re: Primitive recursive vs recursive at the base of the arithmetical hierarchy.
    ... >alternate definitions for the base class of the arithmetical ... >hierarchy. ... recursive relations is not a particularly natural class. ...
    (sci.math)
  • Re: Primitive recursive vs recursive at the base of the arithmetical hierarchy.
    ... >alternate definitions for the base class of the arithmetical ... >hierarchy. ... recursive relations is not a particularly natural class. ...
    (sci.logic)
  • Re: Visitor Pattern Choices
    ... Ok lets say you have a object hierarchy (eg. the Glyph in Lexi from GOF book) and you want to use the visitor pattern. ... So we place an accept method in the the base class glyph and procede to create the visitor hierarchy. ... Thus if every flavor of Glyph needs to interact with the Visitor in a different way, you will need the first solution; if all flavors interact the same way, the second approach works; if Glyph flavors can be grouped by a few common interactions, then something in the middle will work. ...
    (comp.object)
  • Re: Why ABCs make bad Interfaces
    ... Best idiomatic pratice with a C++ base class that is meant to serve as the ... Each derived class should declare the data members it requires. ... Many C++ coders are happily using ABC's as type class hierarchy interfaces. ...
    (comp.object)
  • Why cant static methods be overridden?
    ... Quite often I have a hierarchy of classes where ... I want a specific accessor method to be ... Therefore I specify ... it in the base class. ...
    (comp.lang.java.programmer)