A Machine-Independent Theory of the Complexity of Recursive Functions

Abstract

The number of steps required to compute a function depends, in general, on the type of computer that is used, on the choice of computer program, and on the input-output code. Nevertheless, the results obtained in this paper are so general as to be nearly independent of these considerations.A function is exhibited that requires an enormous number of steps to be computed, yet has a “nearly quickest” program: Any other program for this function, no matter how ingeniously designed it may be, takes practically as many steps as this nearly quickest program.A different function is exhibited with the property that no matter how fast a program may be for computing this function another program exists for computing the function very much faster.