Accession Number:

AD0767730

Title:

Complexity Classes of Recursive Functions

Descriptive Note:

Interim scientific rept.

Corporate Author:

MASSACHUSETTS INST OF TECH CAMBRIDGE PROJECT MAC

Personal Author(s):

Report Date:

1973-06-01

Pagination or Media Count:

96.0

Abstract:

The report is divided into three parts. In part one the properties of honest functions and measured sets as defined by Blum, Meyer and McCreight are developed. An improved proof of the honesty theorem is given and several open problems are solved. In part two the author proves an operator embedding theorem for complexity classes of recursive functions. In part three an extensive survey of research on subrecursive hierarchies is given.

Subject Categories:

  • Theoretical Mathematics

Distribution Statement:

APPROVED FOR PUBLIC RELEASE