# On the Length of Programs for Computing Finite Binary Sequences

@article{Chaitin1966OnTL, title={On the Length of Programs for Computing Finite Binary Sequences}, author={Gregory J. Chaitin}, journal={J. ACM}, year={1966}, volume={13}, pages={547-569} }

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.

#### Topics from this paper

#### 1,094 Citations

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

- Computer Science
- JACM
- 1969

An attempt is made to carry out a program for defining the concept of a random or patternless, finite binary sequence, and for subsequently defining arandom or patterned, infinite binary sequence to be a sequence whose initial segments are all random orpatternless finite binary sequences. Expand

On the difficulty of computations

- Computer Science
- IEEE Trans. Inf. Theory
- 1970

The study of the running time of programs for computing infinite sets of natural numbers leads to an arithmetic of computers, which is a distributive lattice. Expand

Descriptive complexity of computable sequences

- Mathematics
- 2002

Our goal is to study the complexity of infinite binary recursive sequences. We introduce several measures of the quantity of information they contain. Some measures are based on size of programs that… Expand

On the Simplicity and Speed of Programs for Computing Infinite Sets of Natural Numbers

- Computer Science
- J. ACM
- 1969

It is suggested that there are infinite computable sets of natural numbers with the property that no infinite subset can be computed more simply or more quickly than the whole set. Attempts to… Expand

On the Size of Machines

- Mathematics, Computer Science
- Inf. Control.
- 1967

A kind of speedup theorem is proved which is curiously independent of whether the measure of complexity be the size or the number of steps taken by the machines that compute the functions. Expand

A Survey of the Theory of Random Sequences

- Mathematics
- 1977

There are now 10 years that the theory of random sequences revived beginning with a stimulating paper of Kolmogorov in 1965. In this paper Kolmogorov proposed a definition of finite random sequences… Expand

On the algorithmic foundation of information theory

- Computer Science
- IEEE Trans. Inf. Theory
- 1979

The equivalence of the complexity approach and the martingale approach after restriction to effective random tests is used to establish generalized source coding theorems and converses. Expand

Finite approximate approach to the study of the complexity of recursive predicates

- Mathematics
- 1978

An extension of Blum's complexity axiomatics, which enables us to investigate the complexity of bounded approximations of recursive predicates under very general assumptions on the type of the… Expand

Complex Properties of Grammars

- Computer Science
- JACM
- 1980

It is shown that several natural, undecidable properties of grammars are such that the size of the smallest Turing machine which correctly answers questions of length n grows at a nearly maximal rate… Expand

Algorithmic complexity of recursive and inductive algorithms

- Computer Science
- Theor. Comput. Sci.
- 2004

It is demonstrated that for solving many problems inductive Turing machines have much lower complexity than Turing machines and other recursive algorithms. Expand

#### References

SHOWING 1-10 OF 21 REFERENCES

On the Length of Programs for Computing Finite Binary Sequences

- Computer Science
- 1966

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 concer...

On Computable Numbers, with an Application to the Entscheidungsproblem

- Mathematics
- 1937

1. Computing machines. 2. Definitions. Automatic machines. Computing machines. Circle and circle-free numbers. Computable sequences and numbers. 3. Examples of computing machines. 4. Abbreviated… Expand

On the concept of a random sequence

- Mathematics
- 1940

ly the Kollektiv may be represented by an infinite sequence of points of an appropriate space, the Merkmalraum. Or if the number of possible outcomes of a trial is finite (and it may well be argued… Expand

An Introduction to the Theory of Numbers

- Nature
- 1946

THIS book must be welcomed most warmly into X the select class of Oxford books on pure mathematics which have reached a second edition. It obviously appeals to a large class of mathematical readers.… Expand

Theory of Games and Economic Behavior.

- Economics, Mathematics
- 1944

This is the classic work upon which modern-day game theory is based. What began more than sixty years ago as a modest proposal that a mathematician and an economist write a short paper together… Expand

Computability and Unsolvability

- Mathematics, Computer Science
- McGraw-Hill Series in Information Processing and Computers
- 1958

Only for you today! Discover your favourite computability and unsolvability book right here by downloading and getting the soft file of the book. This is not your time to traditionally go to the book… Expand

A mathematical theory of communication

- Computer Science, Mathematics
- Bell Syst. Tech. J.
- 1948

In this final installment of the paper we consider the case where the signals or the messages or both are continuously variable, in contrast with the discrete nature assumed until now. To a… Expand

The Logic of Scientific Discovery

- Philosophy, Economics
- 1934

Described by the philosopher A.J. Ayer as a work of 'great originality and power', this book revolutionized contemporary thinking on science and knowledge. Ideas such as the now legendary doctrine of… Expand