PROPERTIES OF BOUNDS ON COMPUTATION,

Abstract

Partial recursive functions which equal the amount of time or space required by computations have special properties which distinguish them from arbitrary partial recursive functions. Our main result illustrates a property of running times similar in interpretation to Borodin's gap theorem. The proof is based on the construction of difficult to compute characteristic functions which take the value one very infrequently. (Author)

Document Details

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

Entities

People

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

Organizations

  • Carnegie Mellon University

Tags

DTIC Thesaurus Topics

  • Computations
  • Construction
  • Mathematics
  • Recursive Functions

Fields of Study

  • Mathematics

Readers

  • Mathematical Modeling and Probability Theory.
  • Systems Analysis and Design

Technology Areas

  • Space
  • Space - Space Objects