Accession Number : AD0693327
Title : CLASSES OF COMPUTABLE FUNCTIONS DEFINED BY BOUNDS ON COMPUTATION.
Descriptive Note : Doctoral thesis,
Corporate Author : CARNEGIE-MELLON UNIV PITTSBURGH PA DEPT OF COMPUTER SCIENCE
Personal Author(s) : McCreight,Edward M.
Report Date : JUL 1969
Pagination or Media Count : 99
Abstract : The structure of the sets of functions computable in time or space (or some other computational resource) bounded above by t is investigated for recursive functions t. The paper contains three principle results. First, if t0,t1,... is a recursively enumarable increasing sequence of recursive functions, then there is a recursive function t* such that the functions computable in resource bound t* are exactly those computable in resource bound ti for some i. Second, any countable partial order can be isomorphically embedded in the family of t-computable classes of functions, partially ordered by set inclusion. Finally, for any recursive t there is a recursive t' which is (almost) the running time of a program, such that exactly those functions computable in resource bounded by t are computable in resource bounded by t'. (Author)
Descriptors : (*COMPUTER PROGRAMMING, *RECURSIVE FUNCTIONS), MATHEMATICAL LOGIC, MEASURE THEORY, CLASSIFICATION, THEOREMS, THESES
Subject Categories : Theoretical Mathematics
Computer Programming and Software
Distribution Statement : APPROVED FOR PUBLIC RELEASE