On the Length of Programs for Computing Finite Binary Sequences: statistical considerations

ABSTRACT

An attempt is made to carry out a program (outlined in a previous paper) for defining the concept of a random or patternless, finite binary sequence, and for subsequently defining a random or patternless, infinite binary sequence to be a sequence whose initial segments are all random or patternless finite binary sequences. A definition based on the bounded-transfer Turing machine is given detailed study, but insufficient understanding of this computing machine precludes a complete treatment. A computing machine is introduced which avoids these difficulties.

REFERENCES

• 1: Gregory J. Chaitin, On the Length of Programs for Computing Finite Binary Sequences, Journal of the ACM (JACM), v.13 n.4, p.547-569, Oct. 1966 [doi>10.1145/321356.321363]
• 2: YON NEUMANN, J., AND MORGENSTERN, O. Theory of Games and Economic BehaiES, Princeton U. Press, Princeton, N. J., 1953.
• 3: HANDY, G. H., AND WRIGHT, E.M. An Introduction to the Theory of Numbers, Oxford U,. Press, Oxford, 1962.
• 4: FELLER, W. An Introduction lo Probability Theory and Its Applications, Vol. I. Wieley New York, 1964.
• 5: FEINSTEIN, A. Foundations of Information Theory. McGraw-Hill, New York, 19.
• 6: YON MInEs, R. Probability, Statistics, and Truth. Macmillan, New York, 1939.
• 7: KOLMOGOROV, A.N. On tables of random numbers. Sankhya {A}, 25 (1963), 369-376.
• 8: CRUNCH, A. On the concept of a random sequence. Bull. Amer. Math. Sac. 6 (t940), 139 135.
• 9: LOVELAND, D.W. Recursively Random Sequences. Ph.D. DisH., N. Y. U., Jue, 1964,
• 10: --. The Kleene hierarchy classification of recursively random sequences. Trans.amtr Math. Soc. 125 (1966), 497-510.
• 11: A new interpretation of the yon Mises cotcept of random sequence. Z. Math. LAgik Grundlagen Math. 12 (1966), 279-294.
• 12: WALD, A. Die Widerspruchsfreiheit des KoIlectivbegriffes der Wahrseheinlichk?isrechnung. Ergebnisse eines malhemalischen IKolloquiums 8 (1937), 38-72.
• 13: KoaoGonov, A. N. Three approaches to the definition of the concept "quantity in information." Problemy Peredaehi Information 1 (1965), 3-11. (in Russian)
• 14: MARTIN-LF, P. The definition of random sequences. Res. Rep., Inst. Math. Stfi U. of Stockholm, Stockholm, 1966, 21 pp.
• 15: --. The definition of random sequences. Inform. Contr. 9 (1966), 602-619.
• 16: LOFGREN, L. Recognition of order and evolutionary systems. In Computer and Information Science-II Academic Press, New York, 1967 pp. 165-175.
• 17: Michael Levin , Marvin Minsky , Roland Silver, On the Effective Definition of Random Sequence, Massachusetts Institute of Technology, Cambridge, MA, 1962

INDEX TERMS

Primary 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)

Additional Classification:
  F. Theory of Computation
  F.4 MATHEMATICAL LOGIC AND FORMAL LANGUAGES

General Terms:
Performance, Theory, Verification