Accession Number : AD0605291

Title :   HIERARCHIES OF GENERAL RECURSIVE FUNCTIONS AND ORDINAL RECURSION.

Descriptive Note : Technical rept. no. 2,

Corporate Author : CASE INST OF TECH CLEVELAND OHIO

Personal Author(s) : Fabian,Robert S.

Report Date : AUG 1964

Pagination or Media Count : 70

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.

Descriptors :   (*RECURSIVE FUNCTIONS, MATHEMATICAL LOGIC), (*MATHEMATICAL LOGIC, RECURSIVE FUNCTIONS), SET THEORY, NUMBERS, ITERATIONS, FUNCTIONS(MATHEMATICS), THEOREMS

Distribution Statement : APPROVED FOR PUBLIC RELEASE