Accession Number:

AD0688241

Title:

PROPERTIES OF BOUNDS ON COMPUTATION,

Descriptive Note:

Corporate Author:

CARNEGIE-MELLON UNIV PITTSBURGH PA DEPT OF COMPUTER SCIENCE

Personal Author(s):

Report Date:

1969-04-01

Pagination or Media Count:

14.0

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 Borodins gap theorem. The proof is based on the construction of difficult to compute characteristic functions which take the value one very infrequently. Author

Subject Categories:

  • Theoretical Mathematics

Distribution Statement:

APPROVED FOR PUBLIC RELEASE