И снова проблема останова...

Я решил оформить в виде записки мой ответ на один из вопросов читателей ввиду важности затронутой проблемы возможности или невозможности автоматического создания алгоритмов.

Я придерживаюсь того мнения, что автоматическое создание алгоритмов невыполнимо (не путать с автоматическим воспроизведением алгоритма, что решаемо и имеет место в практике IT). Мне кажется, причиной невыполнимости является алгоритмическая неразрешимость проблемы остановки. На практике этот вопрос решается только разработчиком алгоритма, что с точки зрения теории сложности вычислений эквивалентно введению оракула останова.

Оракул невозможно представить алгоритмически, его можно только охарактеризовать. Мне самому это очень интересно и здесь у меня самого множество вопросов. Я как-то наткнулся на интересную публикацию [Bartlett 2010]. В подходе Бартлетта есть спорные вещи: он как креационист предлагает в изучении биологии руководствоваться кроме обычных в науке принципов логики и анализа наблюдений еще и Священным Писанием. Я категорически не могу с этим согласиться, поскольку это методологически неверно. Видимо, это является общим изъяном того, что сегодня именуют креационизмом, и одним из тех пунктов, за которые его критикуют. Мы не можем переводить Откровение в разряд эмпирики, у нас нет такого права ни с точки зрения научного метода, ни с точки зрения истинного религиозного опыта, не укладывающегося в рамки рациональной науки. Однако то, что Бартлетт пишет по поводу распознавания оракулов, представляется мне очень интересным. Он справедливо подчеркивает, что выбор, осуществляемый агентом (ответ оракула), — категория, совершенно отличная от детерминизма законов природы и от стохастики. В добавок к этому могу сослаться на свою записку "Почему я считаю биологическую макроэволюцию практически невозможной". В принципе, там излагаются мысли Дэвида Абеля, с которыми, как мне представляется, нельзя не согласиться.

Почему оракул невозможно представить алгоритмически? Этот вопрос по сути является вариантом вопроса о том, почему существуют невычислимые функции, так называемые busy beavers, значения которых в общем случае можно лишь оценить.

• Например, булева функция, аргументами которой является некоторый алгоритм X и набор данных для X, возвращающая значение 1 в случае, если X останавливается, и 0 в противном случае, является невычислимой.
• Другой пример: функция, возвращающая колмогоровскую сложность произвольной строки символов.

Я не знаю точного ответа. Видимо, здесь вступают какие-то ограничения самого логического рационального процесса мышления. Я хочу сказать, что невозможность просчитать оракул, вероятно, является следствием принимаемых математической логикой "правил игры", удовлетворения ею причинно-следственных связей между явлениями окружающего мира, рассматриваемыми хотя и во взаимной связи, но как отдельные явления. Ведь озарение, интуицию, которые объективно имеют место, вряд ли можно просчитать, то есть это, вероятно, тоже своего рода оракул. Повторюсь, пошагово расписать оракул нельзя, поскольку здесь имеет место взрыв по сложности и по требуемой памяти (NP-трудность, PSPACE-трудность): вам необходимо будет перечислить все случаи, да еще, наверное, и записать их на носителе.

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

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

Литература

1. Jonathan Bartlett (2010): Using Non-Physical Causation in Creation Biology (текст, постер, слайды), Blyth Institute, Technical Papers.