Complexity Classes of Recursive Functions
Interim scientific rept.
MASSACHUSETTS INST OF TECH CAMBRIDGE PROJECT MAC
Pagination or Media Count:
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.
- Theoretical Mathematics