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):
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
Subject Categories:
- Theoretical Mathematics