Колмогоровская сложность.

Определяется для информационного сообщения (текстовой строки) как минимальный размер в битах компьютерной программы, которая может вывести это сообщение. Пример на картинке к посту. Также называется алгоритмической сложностью.

Это соответствует задаче максимального сжатия (архивации) строки данных без потери информации. Существует теорема, что в общем случае колмогоровская сложность алгоритмически невычислима. То есть невозможно определить алгоритм, который будет максимально сжимать произвольное сообщение. Да, можно перебрать все короткие программы, но из-за проблемы остановки, чтобы исключить бесконечные зацикливания, мы должны ограничить максимальное время выполнения программ. При этом остаётся вероятность, что существует более короткая программа, которую мы пропустили, потому что она работала слишком долго.

Колмогоровская сложность длинной строки соответствует энтропии Шеннона, за исключением того, что она невычислима. Энтропию Шеннона мы рассчитываем для строки, анализируя её «алфавит» и частоту появления «символов алфавита». Например, если мы имеем последовательность битов, то можем вычислить энтропию Шеннона для одного бита, пар битов, троек и так далее, каждый раз получая разные значения. А вот колмогоровская сложность соответствует минимальной энтропии Шеннона, но мы не можем её посчитать, потому что не знаем, какой «алфавит» выбрать, чтобы получилось минимальное значение.

Поэтому на практике энтропию Шеннона рассчитывают в рамках выбранного «алфавита», а колмогоровская сложность остаётся идеализацией, теоретическим пределом и недостижимым минимумом.

#Сложность@entropians