HIERARCHIES OF GENERAL RECURSIVE FUNCTIONS AND ORDINAL RECURSION.
Technical rept. no. 2,
CASE INST OF TECH CLEVELAND OHIO
Pagination or Media Count:
The purpose of this work was to examine several ways of imposing partial orderings on various classes of general recursive functions. The objective of these partial orderings, or hierarchies, is to obtain some indication of difficulty of computation of the ordered recursive functions. The problem is approached from two points of view. First, the authors consider the known partial orderings of the primitive recursive and general recursive functions using the methods of Grzegorczyk and Kleene, respectively. Second, using an iteration technique the authors impose a total ordering on classes of general recursive functions obtained by closing a fixed set of initial functions under all applications of substitution, primitive recursion and a finite number of general recursive functionals.