
Accession Number : AD0687494
Title : CLASSES OF COMPUTABLE FUNCTIONS DEFINED BY BOUNDS ON COMPUTATION: PRELIMINARY REPORT.
Descriptive Note : Doctoral thesis,
Corporate Author : CARNEGIEMELLON UNIV PITTSBURGH PA DEPT OF COMPUTER SCIENCE
Personal Author(s) : McCreight,E. M. ; Meyer,A. R.
Report Date : APR 1969
Pagination or Media Count : 30
Abstract : The structure of the functions computable in time or space bounded by t is investigated for recursive functions t. The tcomputable classes are shown to be closed under increasing recursively enumerable unions; as a corollary the primitive recursive functions are shown to equal the tcomputable functions for a certain recursive t. Any countable partial order can be isomorphically embedded in the family of tcomputable classes partially ordered by set inclusion. For any recursive t, there is a recursive t' which is (approximately) equal to an actual running time such that the tcomputable functions equal the t'computable functions. (Author)
Descriptors : (*RECURSIVE FUNCTIONS, SET THEORY), COMPUTER PROGRAMMING, MEASURE THEORY, THEOREMS, THESES
Subject Categories : Theoretical Mathematics
Distribution Statement : APPROVED FOR PUBLIC RELEASE