A Machine-Independent Theory of the Complexity of Recursive Functions
- 1 April 1967
- journal article
- Published by Association for Computing Machinery (ACM) in Journal of the ACM
- Vol. 14 (2), 322-336
- https://doi.org/10.1145/321386.321395
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.Keywords
This publication has 4 references indexed in Scilit:
- On the computational complexity of algorithmsTransactions of the American Mathematical Society, 1965
- Machine dependence of degrees of difficultyProceedings of the American Mathematical Society, 1965
- Real time computationIsrael Journal of Mathematics, 1963
- Classes of predictably computable functionsTransactions of the American Mathematical Society, 1963