Classes of computable functions defined by bounds on computation: Preliminary Report

ABSTRACT

The structure of the functions computable in time or space bounded by t is investigated for recursive functions t. The t-computable classes are shown to be closed under increasing recursively enumerable unions; as a corollary the primitive recursive functions are shown to equal the t-computable functions for a certain recursive t. Any countable partial order can be isomorphically embedded in the family of t-computable classes partially ordered by set inclusion. For any recursive t, there is a recursive t' which is (approximately) equal to an actual running time such that the t-computable functions equal the t'-computable functions.

REFERENCES

• 1: Manuel Blum, A Machine-Independent Theory of the Complexity of Recursive Functions, Journal of the ACM (JACM), v.14 n.2, p.322-336, April 1967 [doi>10.1145/321386.321395]
• 2: Blum, M. Recursive function theory and speed of computation. Can. Bull. of Math., v.9(1966), 745-750.
• 3: Borodin, A. Complexity classes of recursive functions and the existence of complexity gaps, in this volume.
• 4: Cobham, A. The intrinsic computational difficulty of functions. Proc. of 1964 Congress for Logic, Math., and Phil. of Science, North Holland(1964).
• 5: Grzegorczyk, A. Some classes of recursive functions. Rozprawy Matematyczne, Warsaw(1953), 1-46.
• 6: Hennie, F. One-tape, off-line Turing machine computations. Information and Control, v.8 (1965), 553-578.
• 7: Hartmannis, J. and R.E. Stearns. On the computational complexity of algorithms. TAMS, v.117(1965), 285-306.
• 8: Albert R. Meyer , Dennis M. Ritchie, The complexity of loop programs, Proceedings of the 1967 22nd national conference, p.465-469, January 1967, Washington, D.C., United States [doi>10.1145/800196.806014]
• 9: Meyer, A.R. and D.M. Ritchie. A classification of functions by computational complexity. Proc. Hawaii International Conf. on System Sciences, Univ. of Hawaii(1968), 17-19.
• 10: Meyer, A. and P. C. Fischer. On computational speed-up. Conf. Record 9th Annual Symp. on Switching and Automata, IEEE Computer group(1968), 351-355.
• 11: Mostowski, A. Über gewisse universelle relationen. Ann. Soc. Polon. Math., v.17(1938), 117-118.
• 12: Péter, R. Rekursive funktionen. Académiai Kiadó, Budapest(1951).
• 13: Rabin, M.O. Degree of difficulty of computing a function and a partial ordering of recursive sets. Technical Report No. 2, Hebrew Univ., Israel (1960).
• 14: Ritchie, D.M. Program structure and computational complexity. Doctoral dissertation, Harvard Univ.(1969).
• 15: Ritchie, R.W. Classes of predictably computable functions. TAMS, v.106(1963), 139-173.
• 16: Stearns, R.E., J. Hartmannis, and P.M. Lewis. Hierarchies of memory-limited computations. Proc. 6th Annual Symp. on Switching Circuits and Logical Design, IEEE Computer group(1965), 179-190.
• 17: Young, P. R. Toward a theory of enumerations. Conf. Rec. of 9th Annual Symp. on Switching and Automata, IEEE Computer group(1968).
• 18: Paul R. Young, Speed-ups by changing the order in which sets are enumerated (Preliminary Version), Proceedings of the first annual ACM symposium on Theory of computing, p.89-92, May 05-07, 1969, Marina del Rey, California, United States [doi>10.1145/800169.805424]

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.4 MATHEMATICAL LOGIC AND FORMAL LANGUAGES
      F.4.1 Mathematical Logic
          Subjects: Recursive function theory

Additional Classification:
  F. Theory of Computation
  F.1 COMPUTATION BY ABSTRACT DEVICES
      F.1.1 Models of Computation
          Subjects: Bounded-action devices (e.g., Turing machines, random access machines)
      F.1.3 Complexity Measures and Classes
          Subjects: Relations among complexity classes

General Terms:
Algorithms, Languages, Measurement, Theory