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

From: Rex Butler (RexButler_at_hotmail.com)
Date: 10/08/04 

Date: 7 Oct 2004 22:53:27 -0700

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, and the other defines the base class
Delta_0 as the set of (total) *recursive* relations.

Why is this?

I would prefer the first choice, since it seems the set of
(non-primitive) recursive relations properly belongs to the class
Sigma_1. Why?

Because among other things, given a recursive function f: N -> N there
exists a primitive recursive relation F in N^3 such that

    f(x) = y if and only if there exists an e in N such that F(x,e,y).

[Possible Motivation: F(x,e,y) iff e is the Godel coding of a finite
length f-computation which starts with x and ends with y, etc.]

Thus the word "recursive" has "Sigma_1" written all over it.
Comments, Corrections?

Rex Butler
RexButler@hotmail.com

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

Relevant Pages
Loading