Complexity Classes of Recursive Functions

Abstract

An honest function is one whose size honestly reflects its computation time. In 1969 Meyer and McCreight proved the "honesty theorem," which says that for every t, the t-computable functions are the same as the t'computable functions for some honest honest t'.