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

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

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

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

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

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


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


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

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

Обсуждение результатов исследования. Выводы

В этой записи, оканчивающей цикл, посвящённый распознаванию дизайна, мы обсудим результаты нашего исследования и подведём итоги.

Предыдущие записи:

• Энтропия Шеннона и сжатие данных. Часть 1 (теория)


• Энтропия Шеннона и сжатие данных. Часть 2 (пример)


• Колмогоровские структуры (теория)


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


• О спецификации и криптографическом хэшировании. Часть 1 (теория)


• О спецификации и криптографическом хэшировании. Часть 2 (пример)

Обсуждение

Из Таблицы 3 в предыдущей записи видно следующее:

1. Машинный код является алгоритмически простым (относительно низкое значение колмогоровской сложности K), поскольку длина программы — фиксированная величина, не зависящая от размера данных (размер файла изображения, подаваемый на вход программе, может быть очень большим). В оценку длины кратчайшей программы, реализующей алгоритм SHA-256, компилятор добавляет слагаемое C_к, не зависящее от данных; это накладные вычислительные расходы на оптимизацию кода, исполняемого операционной системой. Колмогоровская сложность программного кода низкая, хотя сам программный код как последовательность символов статистически сложен, что видно по относительно высоким значениям энтропии Шеннона.


2. Заметим также, что энтропия машинного кода выше, чем кода на языке С. Этого и следовало ожидать, поскольку машинный код должен иметь меньше структурной избыточности, чем языки программирования, предназначенные для чтения программ человеком.


3. Следует также обратить внимание на то, что энтропия программного кода вне зависимости от языка реализации не достигает максимума: любой язык неизбежно несёт в себе избыточность и неоднозначность. Это скажет любой лингвист. Мы не ставили себе целью доказать это в общем случае. Мы это можем лишь подтвердить, основываясь на результатах нашего исследования.


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


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

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

• Описания случайных слабо сжимаемых конфигураций материи характеризуются высокой сложностью и низкой специфичностью;


• Регулярные структуры характеризуются низкой сложностью (сильно сжимаемы) и высокой специфичностью;

Лишь сигнатура специфической сложности:

сложность (относительно высокая энтропия Шеннона) + специфичность (относительно малая колмогоровская сложность)

представляет собой надёжный классификатор дизайна.

И случайность, и природная регулярность инертны к прагматике (к функции), поэтому естественные природные процессы не направлены и лишены прагматической цели. Естественный отбор, который любят приводить в пример оппоненты, осуществляется только из уже имеющихся функциональных фенотипов и не происходит по критерию будущей функции. Из всего нашего исследования ясно, что модель информации Шеннона, с которой мы здесь работали, не отражает специфического (функционального) аспекта биологической информации. По рассмотренным нами примерам ясно, что и природная регулярность, и случайность являются "киллерами" функциональной информации: невозможно закодировать функцию случайными или регулярными строками: в в первом случае будет наблюдаться высокая сложность с низкой специфичностью, а во втором множественные повторы, то есть низкая сложность и высокая специфичность. Функциональные же строки и сложны по Шеннону, и специфичны одновременно. Единственный известный из опыта источник достаточно сложной функции — интеллект.

Конфигурация материи с	Метрика описания с		Сложность	Специфичность	Класс
	Энтропия Шеннона	Колмогоровская сложность
Жидкость, газ	Высокая	Высокая	Высокая	Низкая	Не дизайн
Графический, аудио или текстовый шум
Кристаллы	Низкая	Низкая	Низкая	Высокая
Интерференционные и конвекционные паттерны, регулярные строки
Художественная и техническая проза	Средняя		Средняя		Дизайн
Машинный код (исполняемые файлы)	Высокая		Высокая
Белок-кодирующие участки ДНК
Функциональные участки линейной белковой структуры

Таблица 1. Характеристики конфигураций материи

( Read more... )