Additional Key Words and Phrases: recursive functions, computational complexity, complex recursive functions, almost everywhere, infinitely often
Selected references
- Manuel Blum. A machine-independent theory of the complexity of recursive functions. Journal of the ACM, 14(2):322-336, April 1967.
- A. Borodin. Complexity classes of recursive functions and the existence of complexity gaps. In Conference Record of ACM Symposium on Theory of Computing, pages 67-78, Marina del Rey, California, 5-7 May 1969.
- A. Borodin. Computational complexity and the existence of complexity gaps. Journal of the ACM, 19(1):158-174, January 1972.
- A. Borodin. Corrigendum: ``Computational complexity and the existence of complexity gaps''. Journal of the ACM, 19(3):576, July 1972.
- F. C. Hennie. One-tape, off-line Turing machine computations. Information and Control, 8(6):553-578, December 1965.
- L. H. Landweber and E. L. Robertson. Recursive properties of abstract complexity classes. Journal of the ACM, 19(2):296-308, April 1972.
- A. R. Meyer and L. J. Stockmeyer. The equivalence problem for regular expressions with squaring requires exponential space. In 13th Annual Symposium on Switching and Automata Theory, pages 125-129, The University of Maryland, 25-27 October 1972. IEEE.
- Edward L. Robertson. Complexity classes of partial recursive functions (preliminary version). In Conference Record of Third Annual ACM Symposium on Theory of Computing, pages 258-266, Shaker Heights, Ohio, 3-5 1971 1971.