On computational speed-up
- 1 October 1968
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- p. 351-355
- https://doi.org/10.1109/swat.1968.18
Abstract
Let F be any effective mapping from total functions on the integers to total functions. Composition and iterated composition are examples of such mappings. The "operator speed-up" theorem in this paper establishes the existence of a computable function f such that for any program computing f(x) in p1(x) steps for all x, there is another program computing f(x) in p2(x) steps and F(p2) ≪ P1 almost everywhere. Thus, there is no best program for f. The notions of "program" and "number of steps" are treated axiomatically, so that the theorem is independent of any particular model of a computing machine. An example of speed-up for Turing machines is considered.Keywords
This publication has 5 references indexed in Scilit:
- A Machine-Independent Theory of the Complexity of Recursive FunctionsJournal of the ACM, 1967
- On the Computational Complexity of AlgorithmsTransactions of the American Mathematical Society, 1965
- Machine dependence of degrees of difficultyProceedings of the American Mathematical Society, 1965
- Classes of Predictably Computable FunctionsTransactions of the American Mathematical Society, 1963
- Gödel numberings of partial recursive functionsThe Journal of Symbolic Logic, 1958