CLASSES OF COMPUTABLE FUNCTIONS DEFINED BY BOUNDS ON COMPUTATION.
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)
Document Details
- Document Type
- Technical Report
- Publication Date
- Jul 01, 1969
- Accession Number
- AD0693327
Entities
People
- Edward M. Mccreight
Organizations
- Carnegie Mellon University