Михаил Чумаков
февраль 2017.
77

Что даёт введение понятия колмогоровской сложности, если она невычислима?

Ответить
Ответить
Комментировать
0
Подписаться
0
1 ответ
Поделиться

...и не учитывает ограничения на ресурсы, можно добавить? Ну, про это можно  много говорить (подробнее см. www.lirmm.fr/~ashen/kolmbook.pdf, введение), но  можно доказывать разные математические результаты (например, закон больших чисел, или нижние оценки на одноленточные машины Тьюринга или ещё что-то) и можно использовать как ориентир на практике (например, идея изменить похожесть файлов x,y сравнением сжатой длины их конкатенации с суммой сжатых длин каждого)

1
-1
Прокомментировать
Ответить