Additional Key Words and Phrases: recursion theory, computational complexity, difficulty of computation, computability, Turing machines, algorithms
Selected papers that cite this one
- John Case. Pseudo-extending computable functions. Information and Control, 56(1/2):100-111, January/February 1983.
- Joel I. Seiferas and Albert R. Meyer. Characterizations of realizable space complexities. Annals of Pure and Applied Logic, 73(2):171-190, 1 June 1995.
- Robert I. Soare. Computational complexity of recursively enumerable sets. Information and Control, 52(1):8-18, January 1982.
Selected references
- Manuel Blum. A machine-independent theory of the complexity of recursive functions. Journal of the ACM, 14(2):322-336, April 1967.
- Albert Meyer and Patrick C. Fischer. On computational speed-up. In Conference Record of 1968 Ninth Annual Symposium on Switching and Automata Theory, pages 351-355, Schenectady, New York, 15-18 October 1968. IEEE.
- Paul R. Young. Speed-ups by changing the order in which sets are enumerated (preliminary version). In Conference Record of ACM Symposium on Theory of Computing, pages 89-92, Marina del Rey, California, 5-7 May 1969.
- Paul R. Young. Toward a theory of enumerations. In Conference Record of 1968 Ninth Annual Symposium on Switching and Automata Theory, pages 334-350, Schenectady, New York, 15-18 October 1968. IEEE.