On minimal-program complexity measures

ABSTRACT

Brief consideration is given to some properties of three measures of complexity based on the length of minimal descriptive programs. Although the measures explicitly deal with finite sequences, the complexity of an infinite sequence can be regarded as a function mapping each positive integer n to the complexity of the initial segment of length n. Some properties of a complexity hierarchy of infinite sequences with respect to one of the measures is considered.

REFERENCES

• 1: J. Hartmanis and R.E. Stearns, "On the Computational Complexity of Algorithms" Transactions of the American Mathematical Society, 117 (May 1965) 285-306.
• 2: R.E. Stearns, J. Hartmanis, and P.M. Lewis II, "Hierarchies of Memory Limited Computations", 1965 IEEE Conf. Record on Switching Circuit Theory and Logical Design, 179-190.
• 3: P.C. Fischer, J. Hartmanis, and M. Blum, "Tape Reversal Complexity Hierarchies", Ninth Annual Symposium on Switching and Automata Theory, IEEE, October, 1968, 373-382.
• 4: 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]
• 5: H. Rogers, Jr., "Godel Numberings of Partial Recursive Functions", J. Symbolic Logic 23,3 (Sept.1958), 331-341.
• 6: D.H. Younger, "Recognition and Parsing of Context Free Languages in Time n3", Inf. and Control, 10:2, 189-208.
• 7: A. Meyer and P.C.Fischer, "On Computational Speedup", Ninth Annual Symposium on Switching and Automata Theory, IEEE, October, 1968, 351-355.
• 8: H. Yamada, "Real-time Computation and Recursive Functions not Real-time Computable", IRE Trans. EC-11 (1962),753-760.
• 9: E. M. McCreight , A. R. Meyer, Classes of computable functions defined by bounds on computation: Preliminary Report, Proceedings of the first annual ACM symposium on Theory of computing, p.79-88, May 05-07, 1969, Marina del Rey, California, United States [doi>10.1145/800169.805423]
• 10: P.R. Young, "Toward a Theory of Enumerations" Ninth Annual Symposium on Switching and Automata Theory, IEEE, October, 1968, 334-350.

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.1 COMPUTATION BY ABSTRACT DEVICES
      F.1.3 Complexity Measures and Classes
          Subjects: Complexity hierarchies

Additional Classification:
  F. Theory of Computation
  F.1 COMPUTATION BY ABSTRACT DEVICES
      F.1.3 Complexity Measures and Classes
  F.4 MATHEMATICAL LOGIC AND FORMAL LANGUAGES
      F.4.1 Mathematical Logic
          Subjects: Recursive function theory

General Terms:
Algorithms, Measurement, Theory