THE COMPLEXITY OF FINITE OBJECTS AND THE DEVELOPMENT OF THE CONCEPTS OF INFORMATION AND RANDOMNESS BY MEANS OF THE THEORY OF ALGORITHMS

TLDR

Kolmogorov introduced the concept of finite‑object complexity as the minimal number of binary symbols needed to recover an object, a definition that depends on decoding and was later refined into an invariant form, while related ideas by Solomonoff and Markov spurred rapid development of the field. This article surveys the fundamental results related to Kolmogorov’s complexity theory and its extensions. The authors conduct a survey of the theoretical developments and applications of Kolmogorov complexity in algorithmic theory. Kolmogorov provided an invariant definition of complexity and used it to define the amount of information in finite objects and the concept of a random sequence, later refined by Martin‑Löf.

Abstract

In 1964 Kolmogorov introduced the concept of the complexity of a finite object (for instance, the words in a certain alphabet). He defined complexity as the minimum number of binary signs containing all the information about a given object that are sufficient for its recovery (decoding). This definition depends essentially on the method of decoding. However, by means of the general theory of algorithms, Kolmogorov was able to give an invariant (universal) definition of complexity. Related concepts were investigated by Solomonoff (U.S.A.) and Markov. Using the concept of complexity, Kolmogorov gave definitions of the quantity of information in finite objects and of the concept of a random sequence (which was then defined more precisely by Martin-Löf). Afterwards, this circle of questions developed rapidly. In particular, an interesting development took place of the ideas of Markov on the application of the concept of complexity to the study of quantitative questions in the theory of algorithms. The present article is a survey of the fundamental results connected with the brief remarks above.