ON THE LENGTH OF PROGRAMS FOR COMPUTING FINITE BINARY SEQUENCES: STATISTICAL CONSIDERATIONS
Gregory J. Chaitin · WORLD SCIENTIFIC eBooks · 1987
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. Key Words and Phrases: computational complexity, sequences, random sequences, Turing machines CR Categories: 5.22, 5.5, 5.6 1.