
Accession Number : AD0693327
Title : CLASSES OF COMPUTABLE FUNCTIONS DEFINED BY BOUNDS ON COMPUTATION.
Descriptive Note : Doctoral thesis,
Corporate Author : CARNEGIEMELLON 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 tcomputable 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