Метажизнь: модель метабиологии Грегори Шатена

Hexbug Nano робот. Источник: amazon.com 

Недавно через блог uncommondescent.com я вышел на работы Грегори Шатена (Gregory Chaitin) по развитию математической теории эволюции. Это замечательные статьи: "The evolution of mutating software" и "Life as Evolving Software". Обе доступны в интернете и представляют собой короткие записки: первая легче для прочтения для неподготовленной в математическом смысле аудитории, чем вторая.

Главная мысль работ такова. Жизнь моделируется как совокупность эволюционирующего программного кода (evolving software) не более заданной длины. Отдельный организм в данной метабиологической модели содержит одну программу. Соревнование, моделирующее естественный отбор, состоит в том, что каждая отдельная программа выдает на выход как можно большее целое число. Чем большее целое число может быть названо, тем более приспособлен организм к среде обитания. Из теории вычислимости известно, что функция BB(N), соответствующая решению данной задачи с комичным названием проблемы усердных бобров (англ. the busy beaver problem - вообще-то  выражение busy beaver означает "трудяга"), невычислима, то есть растет быстрее любой вычислимой функции. Иными словами, в выборе конкретной программы нахождения большого целого числа имеются неограниченные возможности для творчества. Сама вычислительная машина достигает максимальной степени загруженности процессом вычисления значения функции BB(N0) для фиксированного N0. Единственное ограничение -  размер программы должен составлять не более N бит для универсальной машины Тьюринга (машина немного отличается от общепринятой тем, что включает оракул останова, о чем говорится ниже).

Мутации представляют собой изменение программ. Точечные мутации представляют собой инверсию/добавление/удаление одного бита. Эволюция моделируется случайным поиском в пространстве программ. Шаг поиска соответствует  мутации программного кода. Критерий поиска - значение целого числа на выходе программы - является моделью степени приспособленности организма к среде обитания (англ. fitness).

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

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

Выбор задачи об усердных бобрах был обусловлен одной из главных проблем моделирования - необходимостью побороть стагнацию, то есть застревание в локальном максимуме (чем выше уровень приспособленности, тем ниже "желание" организма эволюционировать). На каждом шаге поиска, вероятность выбора очередного организма полагалась обратно пропорциональной числу k мутированных битов между ними, точнее как 1/2^k (так определена метрика в данном пространстве поиска).

Результаты использования модели Шатена таковы.

• При поиске простым перебором (самый медленный сценарий): число мутаций, необходимых для того, чтобы результирующий организм вычислял BB(N), составляет порядка 2^N. 
• При поиске с оптимальным выбором оракулом мутаций на каждом шаге (самый быстрый из всех возможных режимов эволюционирования) число мутаций составляет порядка N.
• При использовании кумулятивной эволюционной модели (дарвиновской, состоящей в случайном выборе большого числа мутаций одновременно) верхняя оценка числа мутаций, полученная на упрощенной модели Шатена, составляет порядка N^2.  

Несмотря на то, что O(N^2) - алгоритмически эффективно, с точки зрения времени жизни Земли (согласно общепринятой модели, 4 с лишним миллиарда лет, или около 10^17 секунд), это слишом долго, как и сам Шатен, кажется, признает в лекции, выложенной в youtube.com. Конечно, это верхняя оценка, а не нижняя. В противном случае, можно было бы распрощаться с классической теорией Дарвина навсегда.

Важно отметить, что Шатен признает, что эволюция (если она имела место, - добавим мы) не является эргодическим процессом, так как поиск параметров реальных биосистем не мог покрыть все пространство состояний за такой короткий промежуток времени в 10^17 секунд. Отсюда вытекает, что единственной достоверной причиной жизни является интеллектуальное вмешательство с целью первоначальной настройки параметров, по крайней мере. А это стандартное в рамках теории Intelligent Design утверждение о необходимости перевода состояния системы (организма) в относительно малые зоны конфигурационного пространства, соответствующие нормальному режиму функционирования (жизнедеятельности).

В заключение нужно еще раз подчеркнуть необходимость наличия оракула в модели Шатена (для всех трех сценариев, включая тупой перебор). Это интересная деталь, открывшая целую лавину полемики на uncommondescent.com (см. комментарии посетителей к статье, посвященной работам Шатена). Хотя сам Шатен полагает, что таким оракулом может выступать естественный отбор, это неочевидно. Дело в том, что ни отбор, ни мутации, по всей видимости, не могут сообщить системе достаточное количество функционально специфической информации (functionally specified complex information in digital form, dFSCI), наблюдаемое лишь в живых организмах и в сложных артефактах (см. David Abel "The First Gene"). По определению dFSCI, основываясь на наблюдениях и выводах из теории вероятности и математической статистики, можно практически исключить случайность и/или необходимость как причины возникновения достаточного количества dFSCI. Слово "практически" означает в данном случае невозможность реализации на практике событий, характеризующихся чрезвычайно малой вероятностью. См. универсальный критерий правдоподобия (David Abel, Universal Plausibility Metric and Principle).

А может быть, все же наличие оракула в шатеновской модели является скрытым признанием невозможности (макро)-эволюции по Дарвину и, соответственно, возможности или даже необходимости интеллектуального вмешательства в реальный процесс жизнедеятельности биосферы?

Cм. также заметку K.Durston. Scientific Case for Intelligent Design.