Последнее открытие Колмогорова? (Колмогоров и алгоритмическая статистика)

Теория вероятностей и ее применения. 2023. Т. 68. № 4. С. 719–750.

Верещагин Н. К., Семенов А. Л., Шень А.

Помимо определения сложности описания конечных объектов (ныне называемой колмогоровской сложностью), Колмогоров наметил несколько способов более детального анализа свойств конечных объектов: сложность с ограничением на ресурсы (1965), структурную функцию (1974), а также понятие (α,β)-стохастичности (1981). Впоследствии выяснилось, что эти понятия по существу эквивалентны (дают одну и ту же кривую в разных координатах).
В этом обзоре мы пытаемся проследить возникновение и развитие этих идей Колмогорова, а также аналогичных идей, независимо предложенных другими авторами.

Ключевые слова: алгоритмическая статистика, колмогоровская сложность, сложность с ограничениями на ресурсы, структурная функция Колмогорова, (α,β)-стохастичность

ПУБЛИКАЦИЯ ПОДГОТОВЛЕНА ПО РЕЗУЛЬТАТАМ ПРОЕКТА: Математические методы в исследованиях сложности определений, сложности вычислений и формальных языков (2023)