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

Эту записку я редактировал коренным образом несколько раз.

Недавно на одном из форумов обсуждался вопрос о том, возможно ли создать алгоритм, могущий создавать другие алгоритмы. Я благодарен Дэвиду Абелю, читателям этого блога и лично Юрию Гармаю (см. комментарии ниже), а также участникам указанного форумного обсуждения за ценные замечания.

Ясно, что анализ алгоритмов "на выходе" сильно затруднен алгоритмической неразрешимостью проблемы остановки машины Тьюринга (the halting problem). Отсюда, кстати, вытекает необходимость оракула останова в модели "метажизни" Gregory Chaitin'а (см. мою записку). 

Вот что говорит по этому поводу Дж. фон Нейман в лекциях (примерно конец 40-х или начало 50-х гг. 20 в.):

Нельзя построить автомат, предсказывающий поведение любого произвольного автомата. Тьюринг доказал, что ... нельзя построить автомат, предсказывающий, за сколько шагов другой автомат, который может решать определенную задачу, в действительности решит ее [1, стр. 75]. 

В [1] фон Нейман неопределенно ссылается на работы Курта Геделя. На запрос редактора лекций фон Неймана о том, что именно мог иметь в виду фон Нейман, сам Гедель ответил так [1, стр. 76]:

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

Задача алгоритмизации построения алгоритмов эквивалентна построению такой машины Тьюринга, которая бы создавала другую машину.  И здесь во всей красе стоит проблема останова, которая должна быть решена. Стохастика и закономерность здесь в принципе не помогут: алгоритм должен создать другой алгоритм, что уже предполагает удовлетворение условия останова (computational halting), для чего необходим оракул (иными словами, агент).

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

У фон Неймана [1] показывается интересная вещь. Он говорит о том, что существует некий фазовый переход по сложности: до определенного момента увеличение сложности автоматов не приводит к взрыву сложности результата, однако после преодоления зоны фазового перехода сложность результата работы автомата (алгоритма, машины Тьюринга) может превосходить сложность самого автомата. По-видимому, то же относится и к вычислительной и термодинамической эффективности. Это, как может показаться, положительно решает проблему эволюции.  Замечу, что это, однако, не означает того, что данный подход не имеет никаких проблем (в частности, проблем, на которые указывает Дэвид Абель, связанных с самой сутью алгоритмов, то есть осмысленного набора предписаний как результата принятия соответствующих решений, приводящих к останову эквивалентной машины Тьюринга).

Мне нужно будет некоторое время на поглощение и анализ результатов фон Неймана, после чего я надеюсь оформить главное в виде записки. Сейчас же я лишь ограничусь тем, что приведу аналогию с квантовыми эффектами. Здесь, видимо, происходит та же самая вещь, что и в физике. С высоты птичьего полета (синергетика, теория динамических систем) все выглядит замечательно. Однако при многократном увеличении возникает множество частных проблем, по-видимому, трудно преодолимых или вообще нерешаемых без введения intelligent agency. Интересно, например, что при обсуждении вопросов репликации у фон Неймана явно присутствует то, что через 40 лет Майкл Бихи назовет irreducible complexity.

Литература

1. Дж.фон Нейман. Теория самовоспроизводящихся автоматов. М., Книжный дом "Либроком", 2009.