Келаврик (кролик-цербер) (kelavrik_0) wrote,
Келаврик (кролик-цербер)
kelavrik_0

Сложность, неуменьшаемая сложность и вероятность возникновения.

Сложность, неуменьшаемая сложность и вероятность возникновения.

      Понятие неуменьшаемой сложности ввёл Бихи, в своей книге «Чёрный ящик Дарвина» (не выложена в интернете). Исходя из этой самой сложности он оценивал вероятность возникновения разных систем. Это понятие было исследовано Перахом в статье Разумный замысел или слепая случайность? К сожалению, анализируя, Перах допустил ряд нечётких утверждений за которые цепляются многие креационисты. Поэтому я решил проанализировать само понятие самостоятельно. Но прежде чем говорить о неуменьшаемой сложности нам придётся разобраться с понятием сложности вообще. Я предлагаю следующее определение: Сложность — количество информации, необходимое для описания системы. Как я понимаю, любое определение сложности так или иначе сводится к данному определению.
      Хочу подчеркнуть особо, в этой статье я разбираю сами понятия, но никак не статью Пераха, работы Бихи или критику Пераха. Это всё служит лишь отправной точкой для размышлений.

Сложность шара

      Для начала оценим сложность идеального геометрического объекта: шара. Как мы знаем, шар определяется одним единственным параметром: радиусом (R). Возьмём для примера конкретное значение: 5.6297…см. Итак у нас 5 цифр, I=5·log2(10). Но стоп, почему мы взяли только 5 цифр, а не 10, не 20?! 5.6297014366570921445…см. Количество информации: I=10·log2(10) или I=20·log2(10). Этот пример ярко показывает, что сложность зависит от степени детализации объекта, а полное описание требует бесконечной сложности. Итак, бессмысленно говорить о сложности не оговорив предварительно уровень детализации. На практике этот уровень более ли менее ясен. Для обычного (состоящего из атомов) шара бессмысленно рассматривать расстояния менее нанометров (10-9м). Это меньше минимального расстояния между ядрами атомов в молекуле водорода. Понятие шара введённое на макро уровне на наноуровне утрачивает смысл. Я уж молчу, о флуктуациях размера.
      Продолжим наш анализ. Я задал размер шара в сантиметрах, а мог бы записать в метрах (0.056297…м), километрах (0.000056297…км), миллиметрах (56.297…мм). Впрочем, всё можно записать в общем виде:
          5.6297…·10-5 км
          5.6297…·10-2 м
          5.6297…·10 0 см
          5.6297…·10 1 мм
При такой записи нам надо добавить к сложности не количество перед числом (или сдвиг запятой), а всего лишь сложность показателя степени. Она вычисляется аналогично: один бит на знак + log2(10). То есть можно измерять в любых единицах и оценка сложности практически не изменится (конечно до тех пор, пока мы работаем с числами в привычном диапазоне). Итоговая сложность: Ip=1+log2(N+1). Здесь N – число учитываемых цифр в числе.
      Пока мы работаем с одними шарами, нам достаточно одного числа (R) для определения конкретного шара. Но если мы работаем с разными объектами, то нам кроме радиуса необходимо знать тип объекта: элипсоид, куб, прямоугольный параллелепипед, n-угольная пирамида, цилиндр и др. При учёте этих объектов к описанной выше сложности необходимо добавить It=log2(К), где К – число объектов. Итак, мы видим, что сложность зависит и от того, что мы признали возможным и невозможным, то есть от языка. Этот вывод нам потребуется в дальнейшем. Но давайте рассмотрим сложность и других объектов. Так элипсоид описывается тремя параметрами, цилиндр двумя, прямоугольный параллелепипед тремя, параллелепипед в общем случае шестью. Итоговая сложность: I=It+m·Ip, здесь m – число параметров описывающих тело данной формы. Максимальная сложность у тел неправильной формы. Для их описания требуется самое большое число параметров, которое к тому же увеличивается при увеличении детализации. В своё время, Волькенштейн оценил сложность мозга на уровне детализации мясника и получил 5 бит. Естественно, сложность мозга с точки зрения учёных изучающих его работу на много порядков выше.
      Итак, разбирая очень простые объекты мы убедились, что сложность объектов сильно зависит от нашего произвола. Мы произвольно выбираем уровень детализации, допустимые объекты и тд. Заметьте, я всё время пользовался десятичной системой исчисления. Это система принимается нами по умолчанию, но никто не запрещает нам принять другие умолчания, а то и вовсе передавать информацию о системе счисления.

Сложность последовательности символов

      Выше мы рассмотрели сложность простых геометрических фигур. Но в природе часто встречаются полимеры с разными звеньями: ДНК, РНК, белки. Для нуклеиновых кислот существует 4 основных звена, а для белка 20. Сложность конкретного полимера нетрудно рассчитать по формулам: L·log2(4)=2L для НК и L·log2(20) для белка. Необходимо отметить, что так мы определяем только сложность последовательности, но не конкретной конформации. Более того, мы пропускаем модифицированные остатки. Это тоже уровень детализации. И хотя для белков первичная структура определяет пространственную, но никто зная последовательность не может предсказать пространственную структуру.
      Пусть у нас есть последовательность нуклеотидов: AAAAAAAAAA. Так и хочется упростить эту запись: A10. Давайте сравним сложность обоих способов записи. В первом случае у нас 4 литеры и информационная ёмкость одной литеры 2 бита. Во втором случае 4 нуклеотида + 10 цифр + две скобки (нам ведь наверняка захочется записывать повторы из нескольких нуклеотидов: (АТ)8) Вместе 16 литер или 4 бита на литеру. Итак первая запись содержит 10·2=20 бит, а вторая 3·4=12 бит. Вроде бы выигрыш очевиден, но если мы захотим передать последовательность: AGAATAGATG, то первый метод нам по прежнему даст 20 бит, но второй даст 40. То есть для нерегулярной последовательности наше упрощение записи привело к усложнению. Этот эффект можно наблюдать и для более развитых способов сжатия. Так я сгенеровал случайный файл длиной 5 000 000 байт (вероятности всех символов от 0 до 255 равны). Длина сжатого zip'ом файла 5 001 644 байт, то есть немного длиннее (на 0.03%). Когда же я сжал файл из одного символа (то есть 1 байт), то получил файл размером 111 байт. Как мы видим, сложность зависит от языка. Этот же факт хорошо известен из теории алгоритмов:
      Метрическая Алгоритмов теория. А. т. можно разделить на дескриптивную (качественную) и метрическую (количественную). Первая исследует алгоритмы с точки зрения устанавливаемого ими соответствия между исходными данными и результатами, к ней относятся, в частности, те алгоритмические проблемы, о которых говорилось в предыдущем разделе. Вторая исследует алгоритмы с точки зрения сложности как самих алгоритмов, так и задаваемых ими "вычислений", т. е. процессов последовательного преобразования конструктивных объектов. Важно подчеркнуть, что сложность алгоритмов и вычислений может определяться различными способами, причём может оказаться, что при одном способе А будет сложнее В, а при другом способе - наоборот. Чтобы говорить о сложности алгоритмов, надо сперва описать какой-либо точный язык для записи алгоритмов и затем под сложностью алгоритма понимать сложность его записи; сложность же записи можно определять различными способами (например, как число символов данного типа, участвующих в записи, или как набор таких чисел, вычисленных для разных типов символов). Чтобы говорить о сложности вычисления, надо уточнить, как именно вычисление представляется в виде цепочки сменяющих друг друга конструктивных объектов и что считается сложностью такой цепочки (только ли число членов в ней - "число шагов" вычисления или ещё учитывается "размер" этих членов и т. п.); в любом случае сложность вычисления зависит от исходного данного, с которого начинается вычисление, поэтому сложность вычисления есть функция, сопоставляющая с каждым объектом из области применимости алгоритма сложность соответствующей цепочки. Разработка методов оценки сложности алгоритмов и вычислений имеет важное теоретическое и практическое значение, однако в отличие от дескриптивной А. т., оформившейся в целостную математическую дисциплину, метрическая А. т. делает лишь первые шаги.
      Самый известный способ подсчёта количества информации был предложен Шенноном. Он учёл то, что разные литеры встречаются с разными вероятностями. Однако анализ его формулы выходит за рамки данной статьи.
      Очень легко создать алгоритм, который сжимает до одного бита любую конкретную последовательность литер, но практически не изменяет длину другой последовательности. Просто надо поместить в приёмник данную последовательность и передавать адрес. Данный пример оставляет ощущение искуственности, но можно придумать много неявных способов уменьшения оценки сложности для одной конкретной последовательности. Шеннон придумал способ сжатия последовательности, учитывая частоты литер. Понятно, что если мы возьмём частоты из самой последовательности, то её сложность будет меньше, чем если мы возьмём их из генеральной совокупности. Продолжим аналогию, мы ведь можем взять частоты не только литер, но и пар литер, троек и тд. Пусть у нас есть некая лишённая закономерностей (повторов и т.п.) последовательность ДНК длиной 400 оснований. Пусть мы взяли из неё частоты восьмёрок оснований. Этим мы фактически её задали. Заметьте, в последовательности не было никаких закономерностей. Поэтому не имеет смысла сложность одного объекта (последовательности), а только сложность объекта как представителя множества аналогичных объектов. Конечно, один объект может входить в разные множества. Так можно рассмотреть множество текстов на русском языке и множество случайных сочетаний русских букв (и знаков препинания). Очевидно, что все представители первого множества входят во второе, но не наоборот. Множество предложений много меньше множества сочетаний литер. Именно поэтому, сложность предложения как представителя первого множества меньше сложности этого же предложения как представителя второго. В то же время слово майдиб не входит в первое множество (нет такого слова в русском языке), его сложность будет бесконечной (или неопределённой) с точки зрения первого множества. Итак, показано, что сложность объекта зависит от множества в которое мы его включили. Выбор множества во многом произволен. Кстати, то же самое мы видели и на геометрических объектах.

Сложность: предварительные итоги

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

Неуменьшаемая сложность и вероятность возникновения системы.

      Как я и говорил в самом начале, идея неуменьшаемой сложности была предложена Бихи. Он предложил удалить из системы всё, без чего система может обойтись (то есть без чего основная функция системы будет работать) и измерять сложность полученной системы. Эту сложность он и называл неуменьшаемой сложностью. В принципе, идея правильная, но смотрим на произвол в определении сложности описанный выше. И уж совсем спорна связь сложности с вероятностью образования. Да в некоторых условиях сложность связана с вероятностью. В самом деле, пусть сгенерирована случайная последовательность нуклеотидов, длиной N. Вероятность встречи этой последовательности: p=4-N. Количество информации или сложность: I = N·log2(4) = -log2(p). Более того, если основания встречаются с разной частотой, то вероятность связана с информацией рассчитанной по формуле Шеннона. Правда, с одной существенной оговоркой: если НК представляет собой случайный сополимер, вероятность встретить в каждой позиции нуклеотид не зависит от других нуклеотидов. Так, вероятность того, что 25% генома Drosophila Virilis будут занимать повторы последовательности ACAAACT ничтожно мала, но именно с такова его доля. (и ещё 16% генома заняты двумя похожими последовательностями, © Льюин “Гены”) Впрочем, не будем задерживаться на данном факте, просто запомним, что вероятность сильно зависит от способа генерации и только выполнии некоторых предположений она связана со сложностью. Но предположим, что посылки верны, и посмотрим конкретные примеры.
      Пусть некая ДНК является функциональной, если в ней встречается последовательность ACAAACT (помянутая выше) и если она имеет длину не менее 1000 оснований. Пусть эта вероятности выпадения нуклеотидов равны и не зависят от предъистории. Опять же, эту последовательность нельзя укоротить, возможно при укорачивании она будет вымываться, или хуже взаимодействовать с ферментом, или … То есть 993 основания играют роль балласта. При выполнении этих посылок у нас 41000≈10602 равновероятных последовательностей. Сложность каждой последовательности 2000 бит. Прошу обратить внимание, это неуменьшаемая сложность по Бихи (естественно неуменьшаемая сложность определена только для функциональных последовательностей!). Вероятность выпадения конкретной последовательности: 4–1000≈10–602. Теперь рассчитаем вероятность выпадения функциональной последовательности. Наша подпоследовательность состоит из 7 оснований, вероятность её выпадения 4–7≈6·10–5. Теперь учтём, что подпоследовательность может встретиться в 993 местах общей последовательности:
p = 1-(1-4–7)993 ≈ 0.06
Вероятность выпадения функциональной последовательности оказалась равной 0.06 вместо 10–600! Согласитесь, разница разительная. А ларчик открывается просто. Да у нас всего 10602 последовательностей, но функциональных последовательностей 6·10600. Оценка же вероятности через сложность никак не учитывает тот факт, что функциональных последовательностей может быть экспоненциально много.
      Приведённый мной пример оставляет чуство неудовлетворённости. Как никак большая часть системы играла роль балласта. В самом деле, мы могли записать функциональную последовательность по другому: Xm–ACAAACT–X993-m, оценить сложность этой записи (см. выше) и вероятность через данную сложность. Правда, при этом мы бы ошиблись как минимум на три порядка при оценке вероятности (за счёт размещения), но не на 600 порядков. Да, это так, но для этого нам надо сначала выделить функциональную подпоследовательность, что не так то просто. Кроме того, если в простых случаях можно показать связь вероятности и сложности, то для сложности рассчитанной сложным образом таковая далеко не очевидна. И потом я сознательно выбрал простой пример, который легко анализировать (рассчитывать вероятность). В реальных же системах вам не удастся отделить “балласт” от функциональных аминокислот или нуклеотидов. Так известно, что ферменты (белки) взаимодействуют с субстратом с помощью небольшого количества аминокислот активного центра. Эти аминокислоты обычно расположены в удалённых участках цепи. Функция остальной части белка каркасная. И никак вам не удастся рассчитать вероятность возникновения белка, катализирующего конкретную реакцию, например расщепляющего перекись водорода. Эту вероятность можно определить только экспериментально. И опять же, очень многое будет зависеть от механизма генерации. Мы ведь не обязаны создавать белки с нуля, можем изменять существующие (отбраковывая развёрнутые).
      А возможна ли высокая вероятность, если у нас довольно большая система (высокая сложность), и все узлы системы работают в равной степени? То есть, если балласта как такового нет в принципе. Да разумеется, приведу математический пример. Пусть у нас есть матрица 3×3:
          a11   a12   a13
          a21   a22   a23
          a31   a32   a33
Элементы матрицы: целые числа от 1 до 100 (включительно), притом все числа равновероятны и не зависят от других элементов матрицы. Пусть функциональной будет любая матрица, у которой детерминант (D) больше нуля (там же см. формулу для рассчёта). Как нетрудно рассчитать, у нас 1009=1018 матриц, соответственно вероятность генерации конкретной матрицы 10–18. Сложность же матрицы I=9·log2(100)≈60 бит. Так вот функциональных матриц у нас будет чуть меньше половины всех возможных. В самом деле, D может быть отрицательным, нулевым и положительным. На миллион сгенерированных матриц у меня получилось 27 матриц с детерминантом равным нулю, то есть ничтожно мало по сравнению с остальными. Детерминант меняет свой знак, если мы меняем местами столбцы матрицы (см. свойство 2). Поэтому каждой матрице с D>0 можно сопоставить матрицу с D<0 (если поменять первый столбец со вторым для определённости). И наоборот, каждой матрице с D<0 можно сопоставить матрицу с D>0. То есть
p+=p-
p+=(1-p0)/2 ≈ 1/2
Здесь p+, p0 и p- вероятности генерации матрицы с положительным, нулевым и отрицательным детерминантами соответственно. Обратите внимание, специфика матрицы (размер 3×3, разброс значений, равновероятность) влияет только на p0, то есть на очень малую величину по сравнению с искомой вероятностью. Мы могли рассмотреть более большие и соответственно более сложные матрицы, вероятность сгенерировать матрицу с заданным свойством (D<0) останется близкой к 1/2. Другими словами, исходные посылки сильно влияли на определение сложности, но слабо влияли на вероятность генерации. И напоминаю, все элементы матрицы одинаково влияют на детерминант. И из матрицы нельзя выбросить элементы, то есть сложность неуменьшаема. Как и в предыдущем примере, сложность оказалась слабо связанной с вероятностью потому, что функциональных последовательностей экспоненциально много, а оценка вероятности через сложность даёт вероятность генерации одной матрицы, а не совокупности матриц с искомой характеристикой.
      Давайте разберём отдельно p0. Как нетрудно заметить, рассчитать вероятность генерации матрицы с D=0 довольно сложно. И это роднит наш искусственный пример с биологическими системами. Вместе с тем заметим, что 2.7·10–5 много больше, чем 10–18, то есть оценки через неуменьшаемую сложность. Пусть у нас была бы одна матрица с D=0. Могли бы мы сделать вывод о разумном происхождении данной матрицы, в противовес случайному? Нам было бы сложно оценить реальную вероятность и оценка через сложность могла бы показаться реальной. Пусть мы бы сгенерировали несколько десятков матриц и не получили бы ни одной с Представьте себе, что мы генерировали бы случайные числа двумя запусками рулетки, да ещё считали бы без компьютера. Естественно, нагенерить миллион матриц, да ещё рассчитать детерминанты нам было бы затруднительно. Примерно в такой же ситуации мы находимся и для биологических систем. Попробуйте сгенерировать хотя бы один белок, не говоря уж о системе свёртывания крови (ССК – пример Бихи), а потом протестировать на функциональность! Между тем в природе есть механизмы генерации. И тут мы натыкаемся на одну проблему: механизм генерации. Ведь вероятность напрямую зависит от него, в отличии от сложности. Пусть мы генерим случайно две строки матрицы, а третью получаем как линейную комбинацию двух первых строк (запрещая числа меньше 1 или больше 100, а так же запрещая нецелые значения):
          a11   a12   a13   ¦   A1
          a21   a22   a23   ¦   A2
          a31   a32   a33   ¦   A3 = x·A1 + y·A2
К примеру:
          65   38    4
          99   42    8
          24   18    1   ¦   A3 = (3/4)·A1 - (1/4)·A2
При такой генерации, мы получим D=0 с вероятностью равной 1. Заметьте, сложность матрицы практически не изменится, даже если мы учтём способ генерации. В самом деле, x и y могут быть нецелыми, отрицательными. Описать их будет не проще, чем третью строку как целое. Да и сложность первых двух строк довольно высока: log2(1012) ≈ 40 бит. И это я придумал один возможный путь генерации дающий D=0, а их можно придумать вагон и маленькую тележку. Более того, используя данный способ генерации мы сделали невозможным ранее высоковероятное событие: D>0. Ну а если мы увеличим матрицу, скажем не 3×3, а 4×4 и будем генерировать последнюю строку, как комбинацию первых. Сложность то возрастёт (сложность трёх первых строк больше, чем сложность матрицы 3×3), а вероятность нуля останется единичной:
          a11   a12   a13   a14   ¦   A1
          a21   a22   a23   a24   ¦   A2
          a31   a32   a33   a34   ¦   A3
          a41   a42   a43   a44   ¦   A4 = x·A1 + y·A2+ z·A3

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


Поскольку тема большая, я вынес обсуждение в отдельную тему.
Tags: неуменьшаемая сложность, эволюция
Subscribe
Comments for this post were disabled by the author