Алгоритмическая специфическая сложность и распознавание дизайна

biosemiotics — 19.12.2025

Давайте ещё раз вернёмся к обсуждению уже знакомой нам задачи, решению которой и посвящён мой блог:

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

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

Для начала напомню, что мы установили:

• Сложность связана с понятием шенноновской информационной энтропии и степенью сжимаемости данных;


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


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

Однако перед нами встала новая проблема: мы видели, что достаточно короткая программа (например, клеточный автомат правило 30) может создавать сложный (то есть очень плохо сжимаемый) паттерн. Клеточный автомат в этом случае является краткой спецификацией сложного паттерна. Достаточно краткая программа типа правила 30 может возникнуть спонтанно в уже сформированной вычислительной среде. Не опровергает ли это наши выводы о специфической сложности как надёжной в смысле отбраковки нулевой гипотезы метрике? Я уже отметил в предыдущих записях, что существование самой вычислительной среды, в которой возможно спонтанное возникновение коротких программ, само по себе уже указывает на дизайн. Но это было лишь краткое замечание. Теперь необходимо разобраться с этой проблемой более подробно.

В этом нам будет помогать Gemini, обученный на соответствующей литературе (работы У.Дембского, Р.Маркса, У. Юэрта, С.Майера и других сторонников гипотезы дизайна.

Понятие алгоритмической специфической сложности (ASC)

Алгоритмическая специфическая сложность (Algorithmic Specified Complexity) вводится, определённая для тройки {конфигурация Х, информационного контекста С и стохастической модели P) как разность самоинформации (информационной ценности, сложности) конфигурации X, и колмогоровской сложности Х в контексте С:

ASC(X,C,P) = I(X) - K(X|C),

где:

• X — наблюдаемое, например, битовая строка или последовательность аминокислот


• I(X) = −log₂(P(X)) — информация (self-information), или сложность; измеряется степень неожиданности (surprisal) наблюдения Х при данном распределении P вероятностей. Низкие значения вероятности соответствуют высокой степени неожиданности (сложности) Х.
  
  
  • Пример: бросаем честную монету 10 раз: конфигурация 1111111111 (10 орлов подряд) имеет вероятность P(X) = (1/2)¹⁰ и сложность 10 бит. Сложность любой другой конфигурации, например, 0101010101 — точно такая же, а именно: 10 бит.
  
  


• K(X|C) — условная колмогоровская сложность Х, то есть длина кратчайшей программы, генерирующей (описание) Х в заданном информационном контексте С. Длины кратчайших программ могут быть существенно различными в разных контекстах (например, если процедура использующая внешний модуль, и программа включающая и процедуру, и модуль). Контекст представляет Измеряет паттерн или регулярность Х.
  
  
  • Пример: строка из 1000 символов 1 может быть получена короткой программой: print "1" 10 times, тогда как программа выдачи на печать случайной строки из символов булева алфавита {0,1} той же длины 1000 будет значительно длиннее: print "0010111...", то есть "напечатать всю строку целиком символ за символом", поскольку случайную строку сжать без потери информации невозможно. В первом случае величина K будет меньше, чем во втором.
  
  


• Разница между информацией и колмогоровской сложностью будет велика в случае сложных и специфичных конфигураций Х. Измеряется степень несоответствия наблюдаемого Х нулевой гипотезе. Напомню, что нулевая гипотеза заключается в предположении о случайном формировании конфигурации Х в рамках стохастической модели P.

Что делает ASC полезной мерой?

Ограниченность вероятности наблюдения объектов, для которых ASC больше или равна α бит:

Pr[ASC(X,C,P) ≥ α] ≤ 2^−α

Для краткости опустим доказательство этого неравенства. Смысл этой оценки состоит в том, что случайное появление конфигураций с высокими значениями ASC является экспоненциально редким независимо от распределения вероятностей в модели Р и контекста С.

Таким образом, если наблюдаемая конфигурация Х характеризуется величиной ASC в 100 бит, случайная генерция Х стохастическим процессом P чрезвычайно маловероятна. Иными словами, относительно высокие значения ASC являются практически надёжным обоснованием для отклонения гипотезы о случайной генерации Х. А это, в свою очередь, при условии отсутствия наблюдений закономерной генерации Х эквивалентно утверждению, что альтернативная гипотеза представляет собой утверждение: Х — дизайн.

Когда мы вычисляем ASC, мы отвечаем на вопрос: "Сколь специфична конфигурация Х относительно того, что мы можем ожидать от стохастической модели P?" Если ASC велико, то мы отклоняем гипотезу о случайной генерации Х стохастическим процессом, описываемым соответствующим распрелением P(X).

Случай относительно простой программы-генератора высокоэнтропийных паттернов

А теперь рассмотрим частое возражение: как быть с простыми программами (клеточными автоматами), которые производят высокоэнтропийные паттерны?

Если в нашей стохастической модели P используется равномерное распределение вероятностей для каждого бита в строке при оценке паттерна, которые производит, скажем правило 30, ASC действительно будет очень высоким: большое значение I(X) минус малое K(X|C).

О чём в данном случае говорит высокое значение ASC? Лишь о несоответствии стохастической модели P конфигурации Х. Метрика ASC выполняет свою роль: гипотеза о случайном происхождении Х в данном случае должна быть отклонена (коль скоро существует простое правило, объясняющее появление Х).

Закон сохранения информации

Авторы, предложившие данную метрику (Дембски, Юэрт, Маркс), утверждают, что даже если существует простое правило, объясняющее сложный паттерн, проблема специфической сложности никуда не исчезла, она просто перенесена в контекст С. Они называют это законом сохранения информации:

• Если простое правило производит высокоэнтропийную конфигурацию, неожиданность (информативность, surprisal) переместилась в контекст С, в которым возникает и функционирует данное правило.


• Если, скажем, правило 30 возникает спонтанно в некоторой системе, вероятность этого события должна быть учтена на уровне стохастической модели всей этой системы. Если правило само достаточно редко или настроено на производство специфического результата, ASC остаётся высоким на уровне всей системы.

Функциональные спецификации

ASC измеряет, насколько наблюдаемый паттерн отклоняется от принятой базовой стохастической модели P. Таких объектов в реальности существует множество, включая неинтересные для нас случаи, не являющиеся дизайнами (кристаллы, фракталы, клеточные автоматы, производящие сложные неспецифичные паттерны, и пр.). Для того, чтобы их исключить, вводят дополнительные условия на спецификацию. Например, рассматривают только функциональные паттерны: скажем, нуклеотидные строки, кодирующие функциональные белки; стартовые конфигурации клеточных автоматов, производящих функциональные паттерны типа Gosper Glider Gun, и т.д.

В статье 2015 г. "Algorithmic Complexity in the Game of Life" указанные выше авторы применяют ASC к функциональным структурам. В работе утверждается, что сложные машины (типа конструктора Gemini) характеризуются высокими значениями ASC не потому, что их спецификациями являются простые математические правила, но вследствие того, что они производятся длинными программами, нацеленными на создание функциональных паттернов, самовоспроизводящихся и движущихся в пространстве игры "Жизнь".

Для формализации функциональных спецификаций на контекст С налагают дополнительные ограничения. Так, Kirk Durston, Jack Szostak, например, используют при задании контекста понятие функциональной цели (functional target): требование существования любого простого описания (программы) паттерна заменяется требованием, чтобы конфигурация обеспечивала заданную функцию (например, связывала кислород). Таким образом, если доля конфигураций, обеспечивающих заданную фиксированную функцию f, в пространстве возможных конфигураций мала, то значение I(X) будет велико. Если конфигурация Х попадает в это подмножество, то Х является функционально-сложной и отвечает функциональной спецификации.

Суммируем сказанное выше. Если "простые правила" возникают спонтанно, производя на выходе конфигурации с высокими значениями ASC, они являются ложноположительными результатами распознавания дизайна только если мы остановимся на анализе получающихся конфигураций. Если же анализировать вероятность появления самих правил, мы увидим, что случайное/спонтанное появление "неинтересных" правил типа правила 30 намного более вероятно, чем правил, производящих функциональные конфигурации типа рибосомы.

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

Активная информация

Активная информация вводится следующим образом:

I₊ = log₂(p_target/q_target),

где:

• q_target — вероятность нахождения целевой конфигурации (например, обеспечивающей заданную функцию) вслепую;


• p_target — вероятность нахождения целевой конифигурации с использованием информационного контекста С (например, поискового алгоритма или правила 30).

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

Пример. Оценим активную информацию для правила 30. Без этого правила, вероятность угадывания паттерна составляет 2^−N для N клеток (с двумя состояниями: on и off). С помощью правила 30 вероятность нахождения паттерна равна 1. Таким образом, количество активной информации относительно велико и составляет:

I₊ = log₂(p_target/q_target) = log₂(1/2^−N) = N бит.

Поиск поиска: в случае "простых" программ проблема сдвигается в сторону контекста

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

• Объект/конфигурация Х: высокая сложность, малая вероятность.


• Поиск/правило/контекст С: эффективное нахождение конфигурации (низкая time complexity).


• Поиск поиска: вопрос "Как был сформирован удачный контекст С?".

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

Пример. Для элементарных автоматов существует всего 256 возмножных правил: каждая клетка имеет два состояния, всего у каждой клетки 8 соседей. Таким образом, размер пространства 2^8 = 256. Далее, если посмотреть по классификации Вольфрама, то размер целевого пространства правил классов 3 и 4, производящих нетривиальные результаты (неповторяющиеся, сложные паттерны) — 30. Поэтому количество активной информации составляет: log₂(1/(30/256)) ≈ 3.1 бит. В случае же сложной биологической функции (например, построение рибосомы) пространство поиска составлено из всех химически и физически возможных конфигураций атомов и является поистине астрономическим. Количество активной информации в этом случае велико.

Итак, когда мы говорим, что высокое значение ASC у паттерна, который был получен правилом 30, — это ложноотрицательный результат? Нет. Рассмотрение активной информации требует ответить на вопрос: "А откуда взялся контекст С, в котором возможно появление и фунционирование правила 30?".

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


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

• Если конфигурация Х сложна, а контекст С представляет собой "дешёвое" правило, которое легко отыскать случайным поиском, количество активной информации для всей системы с учётом контекста невелико;


• Напротив, если конфигурация Х сложна и функциональна, а в качестве контекста С выступает относительно редкое правило (алгоритм), которое трудно отыскать случайным поиском, количество активной информации для системы велико и гипотетический вывод о дизайне такой системы имеет серьёзное статистическое обоснование.

Оставить комментарий

Популярные посты:

niger

Автономные беспилотники в промышленности: внедрение систем мониторинга

• Архив