В этой книге мы не рассматривали подобные вопросы подробно. В самом деле, как мы можем сказать, когда продвигаемся в направлении теоремы, а когда наши поиски — пустая трата времени? Этот вопрос я попытался проиллюстрировать на примере головоломки MU. Разумеется, окончательный ответ на него дать невозможно. Именно в этом — суть Ограничительных Теорем, поскольку если бы мы всегда знали, в каком направлении идти, то могли бы построить алгоритм для доказательства любой теоремы, — а это противоречит Теореме Чёрча. Такого алгоритма не существует. (Предоставляю читателю догадаться, почему это следует из Теоремы Чёрча.) Однако это не означает, что невозможно развить интуитивное чувство того, какие дороги ведут к цели и какие уводят в сторону. Лучшие программы обладают сложной эвристикой, позволяющей им делать заключения в исчислении предикатов так же быстро, как это делают способные люди.
Метод при доказательстве теорем заключается в том, чтобы всегда иметь в виду конечную цель — строчку, которую вы хотите получить. — и использовать это знание при поиске промежуточных шагов. Один из способов, разработанных для превращения общих целей в местную стратегию для деривации, называется упрощением проблем. Он основан на идее, что кроме конечной задачи можно обычно выделить также несколько подзадач, решение которых помогает в нахождении решения основной задачи. Следовательно, если разбить проблему на серию новых подзадач, и каждую из них затем разбить на подподзадачи — и так далее, рекурсивным образом, — то рано или поздно мы придем к очень простым целям, которых можно будет достигнуть за пару шагов. По крайней мере, так кажется…
Именно упрощение проблемы было причиной неприятностей Зенона. Как вы помните, его метод, чтобы попасть из А в Б (где Б было конечной целью), состоял в «упрощении» задачи, разбив ее на две подзадачи сначала пройти половину пути, а затем все остальное. Таким образом, вы «протолкнули» — говоря в терминах главы V — две подзадачи в ваш «стек задач». Каждая из них, в свою очередь, будет заменена на две подзадачи — и так далее, до бесконечности. Вместо единственной конечной цели у вас получается бесконечный стек задач (рис. 115). Вытолкнуть бесконечное количество подзадач из вашего стека будет непросто — именно это, разумеется, и имел в виду Зенон.
Рис. 115. Бесконечное дерево подзадач Зенона, чтобы добраться от А до Б.
Еще один пример бесконечной рекурсии в упрощении проблем можно найти в Диалоге «Маленький Гармонический Лабиринт», когда Ахилл хотел исполнения своего Нетипового Желания. Это должно было быть отложено до тех пор, пока не было получено разрешение Мета-Гения, но чтобы получить разрешение на дачу разрешения, Мета-Гений должна была говорить с Мета-Мета Гением и так далее. Несмотря на бесконечность стека задач, желание Ахилла было все же исполнено. Упрощение задач в конце концов победило!
Хотя я над ним и подсмеиваюсь, упрощение задач является могучим инструментом для превращения сложных конечных целей в более простые местные задачи. Эта техника отлично работает в некоторых ситуациях, таких, например как шахматные эндшпили, где расчет вариантов часто неэффективен, даже когда мы рассчитываем вперед на огромное (15 или более) количество шагов. Это объясняется тем, что чистый расчет вариантов не основан на планировании, вместо поиска определенной цели он просто исследует огромное количество возможных альтернатив. Конечная цель позволяет нам выработать стратегию для ее достижения, а это совершенно иная техника, чем механический расчет вариантов. Разумеется, в технике расчета желательность или нежелательность данного варианта измеряется функцией оценки, которая косвенно включает многие цели, основная из которых — не получить мата. Но это слишком неявно. У хороших шахматистов, играющих против программ, основанных на расчете вариантов обычно складывается впечатление, что те весьма слабы в составлении планов и разработке стратегии.
У нас нет гарантии того, что метод упрощения задач сработает в каждом отдельном случае. Во многих ситуациях он терпит фиаско. Рассмотрим, например, следующую простую задачу. Представьте себе, что вы — собака, и что хозяин только что перекинул вашу любимую кость через забор в соседний двор. Кость видно сквозь щели в заборе, она лежит на траве, и у вас текут слюнки. На расстоянии приблизительно пятнадцати метров от кости вы видите открытую калитку в заборе. Что вы сделаете? Некоторые собаки просто подбегают к забору поближе к кости и начинают лаять. Другие собаки бросаются к калитке (удаляясь при этом от цели) и бегут прямо к лакомому кусочку. Можно сказать, что и те, и другие применяют технику упрощения задачи, разница в том, что они представляют задачу по-разному. Лающая собака видит подзадачи в том, чтобы (1) подбежать к забору, (2) попасть на ту сторону и (3) подбежать к кости, но вторая подзадача оказывается слишком трудной, и собака начинает лаять. Для другой собаки подзадачи заключаются в том, чтобы (1) подбежать к калитке, (2) пробежать сквозь нее и (3) подбежать к кости. Обратите внимание, что все зависит от того, как вы представляете себе «пространство проблемы» — то есть от того, что кажется вам упрощением задачи (движением к цели) и что — усложнением задачи (движением от цели).
Некоторые собаки сначала пытаются подбежать прямо к кости; когда они натыкаются на забор, в их мозгу нечто проясняется и они меняют направление и бегут к калитке. Им становится ясно, что то, что, как им сначала казалось, увеличивает дистанцию между начальным и желанным положениями, — а именно, отдаление от кости и приближение к калитке — на самом деле ее уменьшает. С первого взгляда они принимают физическое расстояние за расстояние проблемы. Любое отдаление от кости кажется им, по определению, Плохой Идеей. Но затем они каким-то образом понимают, что могут изменить свое восприятие того, что на самом деле «приблизит» их к кости. В правильно выбранном абстрактном пространстве движение к калитке является траекторией, приводящей собаку к кости. В этом смысле собака каждую минуту находится все «ближе» к кости. Следовательно, польза упрощения задач зависит от того, каким образом эта задача представлена у вас в голове. То, что в определенном пространстве выглядит как отступление, в ином пространстве может быть революционным шагом вперед.
В повседневной жизни мы постоянно сталкиваемся с необходимостью решать задачи, подобные проблеме собаки и кости. Предположим, как-то вечером я решаю съездить на машине к товарищу, живущему на расстоянии 100 км. на юг; при этом я нахожусь на работе, куда утром приехал на велосипеде. Прежде, чем я окажусь в машине, направляющейся на юг, я должен буду совершить множество кажущихся ошибочными шагов в «неправильном» направлении. Я должен буду выйти из кабинета, направляясь при этом на восток; пройти по коридору к выходу из здания, сначала на север, затем на запад. После этого я поеду домой на велосипеде, поворачивая во всех четырех направлениях. Там, после серии коротких передвижений, я, наконец, попаду в машину. Разумеется, это не означает, что я поеду прямо на юг — мой маршрут может включать повороты на север, восток или запад, чтобы как можно быстрее добраться до шоссе. Это совершенно не кажется мне парадоксальным или забавным; пространство, в котором физическое отступление воспринимается как движение к цели, так глубоко встроено в мой мозг, что я не вижу никакой иронии в том, что мне приходится двигаться на север, чтобы попасть на юг. Дороги, коридоры и так далее действуют как каналы, которые я покорно принимаю как данное; таким образом, моя интерпретация ситуации частично навязывается мне сверху. Но собаке, стоящей перед забором, гораздо труднее это сделать — особенно если прямо перед ее носом лежит аппетитная кость. На самом деле, когда пространство проблемы оказывается лишь немного абстрактнее физического пространства, люди часто бывают также беспомощны, как лающая на забор собака.