HIERARCHIES OF GENERAL RECURSIVE FUNCTIONS AND ORDINAL RECURSION.
Abstract
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.
Document Details
- Document Type
- Technical Report
- Publication Date
- Aug 01, 1964
- Accession Number
- AD0605291
Entities
People
- Robert S. Fabian
Organizations
- Case Western Reserve University