Почему в случае строковых функций "что ни кинь -- всё клин" не получается

Функция, определенная в пространстве Ω строк символов фиксированного алфавита A, по необходимости является разреженной (sparse). Причём степень разреженности тем больше, чем выше сложность функции.

Прежде всего заметим, что функция определена в нашем случае на множестве дискретных переменных.

Функциональная сложность переменной (строки s ∈ Ω) измеряется количеством функциональной информации в строке:

I_f(s) = —log₂(|T_f|/|Ω(A)|),

где:

• Ω(A) -- пространство возможных строк символов алфавита А.


• T_f -- целевое подпространство, включающее лишь строки, доставляющие функцию f.


• |X| -- число элементов множества Х.

Почему функция, определённая в таком пространстве, по необходимости разрежена?

Проиллюстрируем это на простом примере, который мы позаимствуем из замечательной лекции Стивена Майера.

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

Итак, функция кодовой комбинации цифр -- открывать замок. В данном случае:

• А = {0,1,...,9}, |A| = 10.


• |Ω| = 10⁴.


• |T_f| = 1.


• I_f = 4 log₂10 ≈ 13.3 бит.

А теперь представим, что мы увеличили длину L строк на 1 символ, не меняя алфавита. То есть мы купили новый замок, длина кодовой комбинации которого не 4, а 5 цифр. Теперь у нас такая картина:

• |Ω| = 10⁵.


• |T_f| = 1 (число функциональных комбинаций не изменилось).


• I_f = 5 log₂10 ≈ 16.6 бит (количество функциональной информации возросло).

Число функциональных комбинаций осталось тем же самым, а размер пространства увеличился в |A| = 10 раз.

В случае сложных функций размер |T_f| целевого подпространства (то есть фактически число синонимов функциональной строки s) с ростом длины строки L растёт медленнее, чем взрывается размер |Ω| пространства возможных строк:

O(|T_f(L)|) < O(|Ω(L)|).

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

Кстати, Douglas Axe во время оно показал, что для белкового домена средних размеров (если не ошибаюсь, ~150 АА) отдельно взятого белкового семейства (beta-lactamase), редкость функциональных строк оценивается отношением 1 функциональная строка на каждые 10⁷⁷. Причём максимальное число организмов, когда-либо живших за всю историю биосферы, в предположениях, благоприятных для эволюционной парадигмы, Майер оценивает как 10⁴⁰ ≈ 2¹³³ (более оптимистичная для эволюции оценка GPuccio в 2¹⁴⁰ организмов отличается в 2⁷=128 раз). Если использовать оценку Майера, то получается, что доля состояний, которые теоретически могли быть просмотрены эволюцией, за всю её славную и неповторимую историю, в процессе поиска функциональной аминокислотной строки для фермента beta-lactamase, составляет 10⁴⁰/10⁷⁷ = 10^-37. Для осознания масштаба стоящих перед эволюцией задач надо иметь в виду, что размер протеома одноклеточной E.Coli оценивается в 1620-2260 различных типов белков. Как-то многовато для незатейливой схемы RV+NS...