Non-existence of program optimizers in an abstract setting

  • Donald A. Alton
  • John L. Lowther
Theorie De La Programmation Theory Of Programming
Part of the Lecture Notes in Computer Science book series (LNCS, volume 19)


Turing Machine Complexity Measure Partial Function Computable Function Linear Factor 
These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.


  1. 1.
    Alton, D. A., Diversity of speedups and embeddability in computational complexity, Tech. Rep. 73-01, Dept. of Computer Science, Univ. of Iowa, available as Report NSF-OCA-GJ-33168-01 (accession no. PB-221089) from National Technical Information Service, U.S. Dept. of Commerce, Springfield, Va. 22151, to appear in shorter version, J. of Symbolic Logic.Google Scholar
  2. 2.
    —, Non-existence of program optimizers in an abstract setting, Tech. Rep. 73-08, Dept. of Computer Science, Univ. of Iowa, available as Report NSF-OCA-GJ-33168-02 (accession number PB-226 464/AS) from National Technical Information Service, U.S. Dept. of Commerce, Springfield, Va. 22151.Google Scholar
  3. 3.
    —, revision of [2], to appear, J. Comput. System Sci.Google Scholar
  4. 4.
    Blum, M., A machine-independent theory of the complexity of recursive functions, J. Assoc. Comput. Mach. 14, 322–336 (1967).Google Scholar
  5. 5.
    —, On effective procedures for speeding up algorithms, J. Assoc. Comput. Mach. 18, 290–305 (1971).Google Scholar
  6. 6.
    Cobham, A., The intrinsic computational difficulty of functions, in Logic, Methodology, and Philosophy of Science (Proc. 1964 Internat. Conf., ed. Bar-Hillel, North Holland, 1965), 24–30.Google Scholar
  7. 7.
    Constable, R., Two types of hierarchy theorems for axiomatic complexity classes, in Computational Complexity (Courant Comp. Sci. Symp. 7, ed. Rustin, Algorithmics Press, New York, 1973), 37–63.Google Scholar
  8. 8.
    — and Borodin, A., Subrecursive programming languages 1: efficiency and program structure, J. Assoc. Comput. Mach. 19, 526–568 (1972).Google Scholar
  9. 9.
    Cook, S., and Reckhow, R., Time bounded random access machines, J. Comput. System Sci. 7, 354–375 (1973).Google Scholar
  10. 10.
    Grzegorczyk, A., Some classes of recursive functions, Rozprawy Mat. 4 (1953).Google Scholar
  11. 11.
    Hartmanis, J., Computational complexity of random access stored program machines, Math. Systems Theory 5, 232–245 (1971).Google Scholar
  12. 12.
    — and Hopcroft, J., An overview of the theory of computational complexity, J. Assoc. Comput. Mach. 18, 444–475 (1971).Google Scholar
  13. 13.
    Lowther, J., The existence and non-existence of optimizers for subrecursive programming languages, Ph.D. dissertation, The University of Iowa, in preparation.Google Scholar
  14. 14.
    Ritchie, R., Classes of predictably computable functions, Trans. Amer. Math. Soc. 106, 139–173 (1963).Google Scholar
  15. 15.
    Rogers, R., Theory of recursive functions and effective computability, McGraw-Hill, 1967.Google Scholar

Copyright information

© Springer-Verlag Berlin Heidelberg 1974

Authors and Affiliations

  • Donald A. Alton
    • 1
  • John L. Lowther
    • 1
  1. 1.Department of Computer ScienceThe University of IowaIowa CityUSA

Personalised recommendations