DIMACS TR: 96-50

Ranking Primitive Recursions: the Low Grzegorczyk Classes Revisited

Author: Stephen J. Bellantoni


Traditional results in subrecursion theory are integrated with the recent work in ``predicative recursion'' by defining a simple ranking rho of all primitive recursive functions. The hierarchy defined by this ranking coincides with the Grzegorczyk hierarchy at and above the linear-space level. Thus, the result is like an extension of the Schwichtenberg/Muller theorems. A natural series of classes is also obtained down to the first level when primitive recursion is replaced by recursion on notation. This paper is a companion to the author's work showing how to use a suitable definition of proof rank to define weak subsystems of arithmetic containing unbounded inductions.

Paper Available at: ftp://dimacs.rutgers.edu/pub/dimacs/TechnicalReports/TechReports/1996/96-50.ps.gz
DIMACS Home Page