On the Length of Programs for Computing Finite Binary Sequences
- 1 October 1966
- journal article
- Published by Association for Computing Machinery (ACM) in Journal of the ACM
- Vol. 13 (4) , 547-569
- https://doi.org/10.1145/321356.321363
Abstract
The use of Turing machines for calculating finite binary sequences is studied from the point of view of information theory and the theory of recursive functions. Various results are obtained concerning the number of instructions in programs. A modified form of Turing machine is studied from the same point of view. An application to the problem of defining a patternless sequence is proposed in terms of the concepts here developed.Keywords
This publication has 2 references indexed in Scilit:
- A Mathematical Theory of CommunicationBell System Technical Journal, 1948
- On the concept of a random sequenceBulletin of the American Mathematical Society, 1940