Thursday, 8 August 2013

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

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

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

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

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

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

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

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

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

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

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

Литература

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

12 comments:

  1. Если кто не может предсказать поведение любого алгоритма, то и создавать (какие?) алгоритмы он не может?

    ReplyDelete
    Replies
    1. Мы рассматриваем вопрос о создании алгоритма, который может создать другой алгоритм (другие алгоритмы). А это не одно и то же. Проблема остановки - то есть ответ на вопрос, остановится ли заданный алгоритм, получающий на вход определенные данные или нет - алгоритмически неразрешима, то есть для нее не существует общего алгоритма.

      Delete
    2. >А это не одно и то же.
      В чём разница? Даже не обсуждая разницу: пускай никакой автомат (т.е. МТ) не может предсказать результат действия другого автомата, но почему из этого следует невозможность существования хоть какого-то автомата, создающего хоть какие-то автоматы? :)

      Delete
    3. Вместо "предсказать результат действия другого автомата" следует читать "предсказать результат действия произвольного автомата"

      Delete
    4. Действительно, не следует. Существуют же алгоритмы, копирующие сами себя. Признаю свою ошибку.

      Delete
    5. Компьютерные вирусы - пример алгоритмов, создающих другие алгоритмы (свои клоны и мутации).

      Delete
    6. Юрий, я вернулся к обсуждению вопроса с проблемой остановки МТ и алгоритмизации создания алгоритмов. Мне пришлось переработать записку. Я все-таки склонен думать, что в строгом смысле слова алгоритмизация создания алгоритмов без вмешательства агента невозможна. Репликация - да, но это другая задача. Стохастикой Вы не сможете добиться удовлетворения условия остановки. В результате, Ваши мутированные функциональные клоны алгоритмов будут лишь незначительно отличаться от первоначального алгоритма (если вообще они будут существовать). Хотя, разумеется, репликация алгоритмов алгоритмизируема, как я уже сказал (пример - вирусы).

      Delete
    7. Юрий, Вы пишете:

      >А это не одно и то же.
      В чём разница? Даже не обсуждая разницу: пускай никакой автомат (т.е. МТ) не может предсказать результат действия другого автомата, но почему из этого следует невозможность существования хоть какого-то автомата, создающего хоть какие-то автоматы? :)

      Возникает вопрос: какие именно? Какой автомат может создать другой автомат? И насколько другой?

      Если мы рассмотрим алгоритм и его случайные мутации, то необходимо решить вопрос, а есть ли в пространстве мутаций вообще функциональные алгоритмы (кроме точной реплики)?

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

      Алгоритм - это результат принятия решений (choice contingency). Все остальное - фантастика. ИМХО.

      Delete
    8. Мне сложно участвовать в таком диалоге из-за собственных ограничений, и из-за того, что вижу для себя немало темных мест в лексике и в логике, тут видимо, надо Абеля читать и других упомянутых. (Скажем, последнее про "Алгоритм - это результат принятия решений (choice contingency)." я вообще не понял, могу только предположить из общего посыла Ваших сообщений, что это что-то вроде "алгоритмы могут создаваться только разумными существами")

      Но всё же по существу вопроса я хочу кое-что сказать, вернее спросить:

      Человек создаёт алгоритмы. Можно ли, наблюдая эту деятельность, "уловить" оракул, прямо или как необходимость? Вот, скажем, очевидно, что человек (всякий), в принципе, не может взять и сказать, для произвольного алгоритма, как тот себя поведёт на произвольных данных. И никакая МТ не может. При том, что, МТ не ограничена по памяти и по времени, так что человек (как вычислительное устройство), возможно думать, как бы конечный автомат, да ещё с ограничением на время счёта. Но человек может создавать алгоритмы. Почему? Почему МТ не может?

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

      Delete
  2. Юрий,

    Огромное спасибо за интерес к моему блогу. Оракул невозможно алгоритмически просчитать, его можно охарактеризовать. Мне самому это очень интересно и здесь у меня самого множество вопросов. Я как-то наткнулся на интересную публикацию (постер) Using Non-Physical Causation in Creation Biology, автор Jonathan Bartlett. Если погуглить, она легко находится. Кажется, был еще небольшой текст по постеру с таким же названием. Организация, от имени которой работает этот человек, называется Blyth Institute.

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

    Вы спрашиваете о том, почему невозможно. Не знаю, видимо, здесь вступают какие-то ограничения самого логического рационального процесса мышления. Ведь есть же невычислимые функции, так называемые, busy beavers, которые можно лишь оценить снизу и сверху. Иначе говоря, мне кажется, что невозможность просчитать оракул - это следствие принимаемых логикой "правил игры" (причинно-следственных связей). Ведь озарение, интуицию, которые объективно имеют место, вряд ли можно просчитать, то есть это, вероятно, тоже своего рода оракул.

    Уловить оракул, видимо, можно. Но расписать нельзя, поскольку здесь имеет место взрыв по сложности и по требуемой памяти (NP-трудность, PSPACE-трудность): Вам необходимо будет перечислить все случаи, да еще, наверное, и записать их на носителе. Вот как раз узнавание оракулов и является одной из тем, над которыми работает Джонатан Бартлетт.

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

    ReplyDelete
    Replies
    1. И еще небольшое добавление. У Дэвида Абеля есть личный блог тоже на blospot.com, куда он полностью выкладывает свои публикации. Это, на мой взгляд, стоющий автор: ясно мыслит и ясно излагает. http://davidlabel.blogspot.co.uk/

      Delete
    2. И еще одно :) Где-то недавно я видел текст (кажется, в википедии), обсуждавший известную проблему P =/=(?) NP. Там указывалось, что есть, три группы специалистов по вопросам сложности вычислений. Первые уверены в том, что P =/= NP, но пока мы не можем это доказать. Таких большинство. Вторые (очень малая часть) - в том, что P = NP, но мы также не можем это пока доказать. И, наконец, есть еще третье мнение, а именно: эта задача неразрешима, что является следствием принятых при построении теории вычислений допущений и подходов. Мне кажется, то, как построена математика вообще, оставляет этот вопрос принципиально без ответа.

      Delete