Аннотация:
Пытаясь формализовать задачу алгоритмической статистики, Колмогоров
предложил такую модель: для данного объекта (двоичного слова) $x$ мы
ищем хорошую "статистическую модель" – распределение вероятностей на
двоичных словах – можно ограничиться конечными распределениями или
даже равномерными распределениями на конечных множествах. Тогда
"качество" конечного $A$ (содержащего $x$) как модели измеряется двумя
параметрами, предложенными Колмогоровым: его сложностью (модель должна
быть простой) и "дефектом случайности $x$ в $A$" (модель должна
улавливать все закономерности в $x$ — $x$ должно быть "типичным
элементом $A$"). Имея слово $x$, мы можем изучать, какие комбинации
этих параметров реализуемы ($\alpha$-$\beta$-стохастичность). Другой
подход - искать "двухчастные описания" $x$ – сначала задаётся
множество, а затем порядковый номер $x$ в этом множестве; этому
подходу соответствует "структурная функция", предложенная
Колмогоровым. Наконец, можно изучать колмогоровскую сложность с
ограничением на время. Родственные подходы изучались под названием
logical depth и sophistication разными авторами. В последние полтора
десятилетия выяснилось, что с логарифмической точностью они
оказываются эквивалентными – и хотя с практической точки зрения
ограничения на время, тут появляющиеся, неразумно большие, но это
важный нетривиальный результат о колмогоровской сложности (Беннетт,
Витаньи, Верещагин, Бауэенс, другие.).
|
