Geodesic
Kolmogorov’s last discovery? (Kolmogorov and algorithmic statistics)
Teoriâ veroâtnostej i ee primeneniâ, Tome 68 (2023) no. 4, pp. 719-750

Voir la notice de l'article provenant de la source Math-Net.Ru

The definition of descriptional complexity of finite objects suggested by Kolmogorov and other authors in the mid-1960s is now well known. In addition, Kolmogorov pointed out some approaches to a more fine-grained classification of finite objects, such as the resource-bounded complexity (1965), structure function (1974), and the notion of $(\alpha,\beta)$-stochasticity (1981). Later it turned out that these approaches are essentially equivalent in that they define the same curve in different coordinates. In this survey, we try to follow the development of these ideas of Kolmogorov as well as similar ideas suggested independently by other authors.
Keywords: Kolmogorov complexity, algorithmic statistics, resource-bounded complexity, Kolmogorov's structure function, $(\alpha,\beta)$-stochasticity. 
@article{TVP_2023_68_4_a3,
     author = {N. K. Vereshchagin and A. L. Semenov and A. Kh. Shen'},
     title = {Kolmogorov{\textquoteright}s last discovery? {(Kolmogorov} and algorithmic statistics)},
     journal = {Teori\^a vero\^atnostej i ee primeneni\^a},
     pages = {719--750},
     publisher = {mathdoc},
     volume = {68},
     number = {4},
     year = {2023},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/TVP_2023_68_4_a3/}
}
TY  - JOUR
AU  - N. K. Vereshchagin
AU  - A. L. Semenov
AU  - A. Kh. Shen'
TI  - Kolmogorov’s last discovery? (Kolmogorov and algorithmic statistics)
JO  - Teoriâ veroâtnostej i ee primeneniâ
PY  - 2023
SP  - 719
EP  - 750
VL  - 68
IS  - 4
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/TVP_2023_68_4_a3/
LA  - ru
ID  - TVP_2023_68_4_a3
ER  - 
%0 Journal Article
%A N. K. Vereshchagin
%A A. L. Semenov
%A A. Kh. Shen'
%T Kolmogorov’s last discovery? (Kolmogorov and algorithmic statistics)
%J Teoriâ veroâtnostej i ee primeneniâ
%D 2023
%P 719-750
%V 68
%N 4
%I mathdoc
%U http://geodesic.mathdoc.fr/item/TVP_2023_68_4_a3/
%G ru
%F TVP_2023_68_4_a3
N. K. Vereshchagin; A. L. Semenov; A. Kh. Shen'. Kolmogorov’s last discovery? (Kolmogorov and algorithmic statistics). Teoriâ veroâtnostej i ee primeneniâ, Tome 68 (2023) no. 4, pp. 719-750. http://geodesic.mathdoc.fr/item/TVP_2023_68_4_a3/