Accession Number:

AD0687494

Title:

CLASSES OF COMPUTABLE FUNCTIONS DEFINED BY BOUNDS ON COMPUTATION: PRELIMINARY REPORT.

Descriptive Note:

Doctoral thesis,

Corporate Author:

CARNEGIE-MELLON UNIV PITTSBURGH PA DEPT OF COMPUTER SCIENCE

Personal Author(s):

• McCreight,E. M.
• Meyer,A. R.

Report Date:

1969-04-01

Pagination or Media Count:

30.0

Abstract:

The structure of the functions computable in time or space bounded by t is investigated for recursive functions t. The t-computable classes are shown to be closed under increasing recursively enumerable unions as a corollary the primitive recursive functions are shown to equal the t-computable functions for a certain recursive t. Any countable partial order can be isomorphically embedded in the family of t-computable 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 t-computable 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