Degrees of Total Algorithms versus Degrees of Honest Functions

摘要

We prove a few theorems elucidating the relationship between to different approaches to subrecursive degree theory. One approach has its roots in the theory of algorithms and Turing degrees. The other approach has its roots in subrecursive hierarchies of fast-growing functions.