Даглас Хофштадтер - ГЕДЕЛЬ, ЭШЕР, БАХ: эта бесконечная гирлянда

Вернемся теперь к истории ИИ. Одним из ранних шагов в этом направлении была попытка создания программы, способной доказывать теоремы. Концептуально это то же самое, что создание программы, способной искать деривацию MU в системе MIU — с той разницей, что формальные системы здесь часто были сложнее, чем система MIU. Это были версии исчисления предикатов, представляющего собой расширенный — с использованием кванторов — вариант исчисления высказываний. В действительности большинство правил исчисления предикатов содержится в ТТЧ. Трюк при написании такой программы заключается в том, чтобы снабдить ее чувством направления, чтобы программа не блуждала по всему пространству возможностей, а следовала лишь по «важным» тропинкам, которые, в соответствии с некими разумными критериями могут привести к нужной строчке.

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

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

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

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

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

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

У нас нет гарантии того, что метод упрощения задач сработает в каждом отдельном случае. Во многих ситуациях он терпит фиаско. Рассмотрим, например, следующую простую задачу. Представьте себе, что вы — собака, и что хозяин только что перекинул вашу любимую кость через забор в соседний двор. Кость видно сквозь щели в заборе, она лежит на траве, и у вас текут слюнки. На расстоянии приблизительно пятнадцати метров от кости вы видите открытую калитку в заборе. Что вы сделаете? Некоторые собаки просто подбегают к забору поближе к кости и начинают лаять. Другие собаки бросаются к калитке (удаляясь при этом от цели) и бегут прямо к лакомому кусочку. Можно сказать, что и те, и другие применяют технику упрощения задачи, разница в том, что они представляют задачу по-разному. Лающая собака видит подзадачи в том, чтобы (1) подбежать к забору, (2) попасть на ту сторону и (3) подбежать к кости, но вторая подзадача оказывается слишком трудной, и собака начинает лаять. Для другой собаки подзадачи заключаются в том, чтобы (1) подбежать к калитке, (2) пробежать сквозь нее и (3) подбежать к кости. Обратите внимание, что все зависит от того, как вы представляете себе «пространство проблемы» — то есть от того, что кажется вам упрощением задачи (движением к цели) и что — усложнением задачи (движением от цели).

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