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