Gregory J. Chaitin
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.
- 1 CHAITIN, G. J. On the length of programs for computing finite binary sequeuceu J ACM 18, 4 (Oct. 1966), 547-569. Google Scholar
- 2 YON NEUMANN, J., AND MORGENSTERN, O. Theory of Games and Economic BehaiES, Princeton U. Press, Princeton, N. J., 1953.Google Scholar
- 3 HANDY, G. H., AND WRIGHT, E.M. An Introduction to the Theory of Numbers, Oxford U,. Press, Oxford, 1962.Google Scholar
- 4 FELLER, W. An Introduction lo Probability Theory and Its Applications, Vol. I. Wieley New York, 1964.Google Scholar
- 5 FEINSTEIN, A. Foundations of Information Theory. McGraw-Hill, New York, 19.Google Scholar
- 6 YON MInEs, R. Probability, Statistics, and Truth. Macmillan, New York, 1939.Google Scholar
- 7 KOLMOGOROV, A.N. On tables of random numbers. Sankhya {A}, 25 (1963), 369-376.Google Scholar
- 8 CRUNCH, A. On the concept of a random sequence. Bull. Amer. Math. Sac. 6 (t940), 139 135.Google Scholar
- 9 LOVELAND, D.W. Recursively Random Sequences. Ph.D. DisH., N. Y. U., Jue, 1964,Google Scholar
- 10 --. The Kleene hierarchy classification of recursively random sequences. Trans.amtr Math. Soc. 125 (1966), 497-510.Google ScholarCross Ref
- 11 A new interpretation of the yon Mises cotcept of random sequence. Z. Math. LAgik Grundlagen Math. 12 (1966), 279-294.Google ScholarCross Ref
- 12 WALD, A. Die Widerspruchsfreiheit des KoIlectivbegriffes der Wahrseheinlichk?isrechnung. Ergebnisse eines malhemalischen IKolloquiums 8 (1937), 38-72.Google Scholar
- 13 KoaoGonov, A. N. Three approaches to the definition of the concept "quantity in information." Problemy Peredaehi Information 1 (1965), 3-11. (in Russian)Google Scholar
- 14 MARTIN-LF, P. The definition of random sequences. Res. Rep., Inst. Math. Stfi U. of Stockholm, Stockholm, 1966, 21 pp.Google Scholar
- 15 --. The definition of random sequences. Inform. Contr. 9 (1966), 602-619.Google ScholarCross Ref
- 16 LOFGREN, L. Recognition of order and evolutionary systems. In Computer and Information Science-II Academic Press, New York, 1967 pp. 165-175.Google Scholar
- 17 LKEVIN, M., MINSKY, M., AND SILVER R. On the problem of the effective definition of sequence", Memo 36 (revised), RLE and MIT Comput. Center, 1962, 10 pp. Google Scholar
Index Terms
- On the Length of Programs for Computing Finite Binary Sequences: statistical considerations
Recommendations
Pseudo-Random Number Generator Based on Binary and Quinary Maximal-Length Sequences
A new pseudo-random generator for decimal numbers is presented. A sequence of decimal digits is obtained by combining a binary and a quinary maximal-length sequence generated by feedback shift-register circuits. The autocorrelation sequence (ACS) of the ...
New optimal binary sequences with period 4p via interleaving Ding---Helleseth---Lam sequences
Binary sequences play important roles in radar, communication, and cryptography. Finding new binary sequences with optimal autocorrelation value/magnitude has been an interesting research topic in sequence design. Ding---Helleseth---Lam sequences are ...
Barker sequences of odd length
A Barker sequence is a binary sequence for which all nontrivial aperiodic autocorrelations are at most 1 in magnitude. An old conjecture due to Turyn asserts that there is no Barker sequence of length greater than 13. In 1961, Turyn and Storer gave an ...
Comments