Kolmogorov Last Discovery? (Kolmogorov and Algorithmic Statictics)
А. Н. Семенов, Alexander Shen, Nikolay Vereshchagin
Abstract
Open-access reader
А. Н. Семенов, Alexander Shen, Nikolay Vereshchagin
Abstract
Open-access reader
The last theme of Kolmogorov's mathematics research was algorithmic theory of information, now often called Kolmogorov complexity theory. There are only two main publications of Kolmogorov (1965 and 1968-1969) on this topic. So Kolmogorov's ideas that did not appear as proven (and published) theorems can be reconstructed only partially based on work of his students and collaborators, short abstracts of his talks and the recollections of people who were present at these talks. In this survey we try to reconstruct the development of Kolmogorov's ideas related to algorithmic statistics (resource-bounded complexity, structure function and stochastic objects).
A significance statement is not available in the OpenAlex record.
A contribution statement is not available in the OpenAlex record.
Method details are not available in the OpenAlex metadata.
Findings are not separately available in the OpenAlex metadata.
Limitations are not available in the OpenAlex metadata.
Application details are not available in the OpenAlex metadata.
The last theme of Kolmogorov's mathematics research was algorithmic theory of information, now often called Kolmogorov complexity theory. There are only two main publications of Kolmogorov (1965 and 1968-1969) on this topic. So Kolmogorov's ideas that did not appear as proven (and published) theorems can be reconstructed only partially based on work of his students and collaborators, short abstracts of his talks and the recollections of people who were present at these talks. In this survey we try to reconstruct the development of Kolmogorov's ideas related to algorithmic statistics (resource-bounded complexity, structure function and stochastic objects).
Key concepts: Kolmogorov complexity, Kolmogorov structure function, Kolmogorov equations (Markov jump process), Theme (computing), Kolmogorov–Smirnov test, Computer science, Bounded function, Mathematics