Понятие воспроизводимого кода

[mns2012]

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

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

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

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

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


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


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

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