mns2012

Размер сжатого файла изображения является хорошим практическим приближением сверху колмогоровской сложности для данных, вследствие эффективности алгоритмов PNG. Однако в общем случае программа в определении колмогоровской сложности должна удовлетворять условиям воспроизводимости.

Воспроизводимый код — это кратчайшая программа P в определении колмогоровской сложности. Приведём это определение ещё раз:

K(x) = min_P { L(P) : P выводит x и останавливается }.

Воспроизводимый код должен быть:

Генеративным: код P, на вход которого подаются фиксированные данные, должен выводить целевой объект x (например, изображение или соответствующее значение криптографического хэша) как свой единственный результат.

Эффективно вычислимым: код должен быть исполняем на тьюринг-полной машине, т.е., попросту говоря, на любом компьютере.

Самодостаточным и минимальным: Код должен включать только алгоритм и необходимые данные. Он не должен содержать:
- избыточные инструкции (лишние циклы, неиспользуемые функции);
- избыточные данные (длинные комментарии, неиспользуемые переменные, синтаксический "мусор" вроде пробелов и форматирования, которые легко сжимаются);
- внешние зависимости (например, вызовы библиотек, которые не включены в длину P).

Для нашего изображения клякс воспроизводимым кодом была бы программа, которая читает сжатый PNG файл (24,279 бит) и распаковывает его в исходный массив пикселей (146,095 байт).