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

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)

Document Details

Document Type
Technical Report
Publication Date
Apr 01, 1969
Accession Number
AD0687494

Entities

People

  • A. R. Meyer
  • E. M. Mccreight

Organizations

  • Carnegie Mellon University

Tags

DTIC Thesaurus Topics

  • Computations
  • Defects (Materials)
  • Inclusions
  • Mathematics
  • Recursive Functions

Fields of Study

  • Mathematics

Readers

  • Mathematical Modeling and Probability Theory.

Technology Areas

  • Space
  • Space - Space Objects