On the Length of Programs for Computing Finite Binary Sequences
- 1 January 1969
- journal article
- Published by Association for Computing Machinery (ACM) in Journal of the ACM
- Vol. 16 (1), 145-159
- https://doi.org/10.1145/321495.321506
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.Keywords
This publication has 3 references indexed in Scilit:
- The definition of random sequencesInformation and Control, 1966
- The Kleene hierarchy classification of recursively random sequencesTransactions of the American Mathematical Society, 1966
- A New Interpretation of the von Mises' Concept of Random SequenceMathematical Logic Quarterly, 1966