|
Последнее открытие Колмогорова? (Колмогоров и алгоритмическая статистика)
Н. К. Верещагинab, А. Л. Семёновa, А. Х. Шеньc a Московский государственный университет имени М. В. Ломоносова, Москва, Россия
b Национальный исследовательский университет "Высшая школа экономики", Москва, Россия
c LIRMM, Univ Montpellier, CNRS, Montpellier, France
Аннотация:
Помимо определения сложности описания конечных объектов (ныне называемой колмогоровской сложностью), Колмогоров наметил несколько способов более детального анализа свойств конечных объектов: сложность с ограничением на ресурсы (1965), структурную функцию (1974), а также понятие $(\alpha,\beta)$-стохастичности (1981). Впоследствии выяснилось, что эти понятия по существу эквивалентны (дают одну и ту же кривую в разных координатах).
В этом обзоре мы пытаемся проследить возникновение и развитие этих идей Колмогорова, а также аналогичных идей, независимо предложенных другими авторами.
Ключевые слова:
колмогоровская сложность, алгоритмическая статистика, сложность с ограничениями на ресурсы, структурная функция Колмогорова, $(\alpha,\beta)$-стохастичность.
Поступила в редакцию: 14.04.2023 Принята в печать: 18.09.2023
Образец цитирования:
Н. К. Верещагин, А. Л. Семёнов, А. Х. Шень, “Последнее открытие Колмогорова? (Колмогоров и алгоритмическая статистика)”, Теория вероятн. и ее примен., 68:4 (2023), 719–750; Theory Probab. Appl., 68:4 (2024), 582–606
Образцы ссылок на эту страницу:
https://www.mathnet.ru/rus/tvp5650https://doi.org/10.4213/tvp5650 https://www.mathnet.ru/rus/tvp/v68/i4/p719
|
Статистика просмотров: |
Страница аннотации: | 288 | PDF полного текста: | 6 | Список литературы: | 45 | Первая страница: | 37 |
|