DIMACS TR: 96-50
Ranking Primitive Recursions: the Low Grzegorczyk Classes Revisited
Author: Stephen J. Bellantoni
ABSTRACT
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