Complexity Classes of Recursive Functions
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.
Document Details
- Document Type
- Technical Report
- Publication Date
- Jun 01, 1973
- Accession Number
- AD0767730
Entities
People
- Robert Moll
Organizations
- Massachusetts Institute of Technology