Гёдель, Эшер, Бах. Эта бесконечная гирлянда

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

Метод при доказательстве теорем заключается в том, чтобы всегда иметь в виду конечную цель — строчку, которую вы хотите получить. — и использовать это знание при поиске промежуточных шагов. Один из способов, разработанных для превращения общих целей в местную стратегию для деривации, называется упрощением проблем. Он основан на идее, что кроме конечной задачи можно обычно выделить также несколько подзадач, решение которых помогает в нахождении решения основной задачи. Следовательно, если разбить проблему на серию новых подзадач, и каждую из них затем разбить на подподзадачи — и так далее, рекурсивным образом, — то рано или поздно мы придем к очень простым целям, которых можно будет достигнуть за пару шагов. По крайней мере, так кажется…

Именно упрощение проблемы было причиной неприятностей Зенона. Как вы помните, его метод, чтобы попасть из А в Б (где Б было конечной целью), состоял в «упрощении» задачи, разбив ее на две подзадачи сначала пройти половину пути, а затем все остальное. Таким образом, вы «протолкнули» — говоря в терминах главы V — две подзадачи в ваш «стек задач». Каждая из них, в свою очередь, будет заменена на две подзадачи — и так далее, до бесконечности. Вместо единственной конечной цели у вас получается бесконечный стек задач (рис. 115). Вытолкнуть бесконечное количество подзадач из вашего стека будет непросто — именно это, разумеется, и имел в виду Зенон.

Рис. 115. Бесконечное дерево подзадач Зенона, чтобы добраться от А до Б.

Еще один пример бесконечной рекурсии в упрощении проблем можно найти в Диалоге «Маленький Гармонический Лабиринт», когда Ахилл хотел исполнения своего Нетипового Желания. Это должно было быть отложено до тех пор, пока не было получено разрешение Мета-Гения, но чтобы получить разрешение на дачу разрешения, Мета-Гений должна была говорить с Мета-Мета Гением и так далее. Несмотря на бесконечность стека задач, желание Ахилла было все же исполнено. Упрощение задач в конце концов победило!

Хотя я над ним и подсмеиваюсь, упрощение задач является могучим инструментом для превращения сложных конечных целей в более простые местные задачи. Эта техника отлично работает в некоторых ситуациях, таких, например как шахматные эндшпили, где расчет вариантов часто неэффективен, даже когда мы рассчитываем вперед на огромное (15 или более) количество шагов. Это объясняется тем, что чистый расчет вариантов не основан на планировании, вместо поиска определенной цели он просто исследует огромное количество возможных альтернатив. Конечная цель позволяет нам выработать стратегию для ее достижения, а это совершенно иная техника, чем механический расчет вариантов. Разумеется, в технике расчета желательность или нежелательность данного варианта измеряется функцией оценки, которая косвенно включает многие цели, основная из которых — не получить мата. Но это слишком неявно. У хороших шахматистов, играющих против программ, основанных на расчете вариантов обычно складывается впечатление, что те весьма слабы в составлении планов и разработке стратегии.

Шанди и кость