3.26. Разрыв вычислительных петель

Попробую осветить полученный вывод под несколько иным углом зрения. Предположим, что, пытаясь обойти налагаемые теоремой Гёделя ограничения, некто решил построить такого ро­бота, который будет способен каким-либо образом «выскакивать из системы» всякий раз, когда управляющий им алгоритм попадет в вычислительную петлю. В конце концов именно постоянное приложение теоремы Гёделя не позволяет нам спокойно при­нять предположение о том, что математическое понимание можно объяснить посредством вычислительных процедур, поэтому, как мне кажется, стоит рассмотреть с этой точки зрения трудности, с которыми сталкивается любая вычислительная модель матема­тического понимания при встрече с теоремой Гёделя.

Мне кто-то говорил, что где-то живут ящерицы, тупость ко­торых настолько велика, что они, подобно «обычным компьюте­рам и некоторым насекомым», способны «зацикливаться». Если несколько таких ящериц поместить на край круглого блюда, то они в вечной «гонке за лидером» будут бегать по кругу до тех пор, пока не умрут от истощения. Смысл этой истории в том, что подлинно интеллектуальная система должна располагать какими-то средствами для разрыва таких петель, тогда как ни один из существующих компьютеров подобными качествами, вообще го­воря, не обладает. (Проблему «разрыва петель» рассматривал Хофштадтерв[200].)

Вычислительная петля простейшего типа возникает, когда система на некотором этапе своей работы возвращается назад, в точности в то же состояние, в каком она пребывала на некотором предыдущем этапе. В отсутствие ввода каких-то дополнитель­ных данных она будет просто повторять одно и то же вычис­ление бесконечно. Не составляет большой трудности построить систему, которая, в принципе, будет гарантированно (пусть и не слишком эффективно) выбираться из петель подобного рода по мере их возникновения (скажем, посредством ведения списка всех состояний, в которых оказывается система, и проверки на каждом этапе на предмет выяснения, не встречалось ли такое состояние когда-либо раньше). Существует, однако, множество других возможных типов петель, причем гораздо более слож­ных. Собственно говоря, проблеме образования петель посвяще­на большая часть рассуждений главы 2 (в особенности, §§2.1 — 2.6), так как вычисление, застрявшее в петле, есть не что иное, как вычисление, которое не завершается. Собственно говоря, под  -высказыванием мы как раз и понимаем утверждение о том, что некоторое вычисление образует петлю (см. §2.10, коммен­тарий к возражению). А еще в § 2.5 мы имели возможность убедиться в том, что факт незавершаемости вычисления (т. е. об­разования петли) однозначно установить с помощью одних лишь алгоритмических методов невозможно. Более того, как можно заключить из вышеприведенных рассуждений, процедуры, по­средством которых математики-люди устанавливают, что данное конкретное вычисление действительно образует петлю (т. е. уста­навливают истинность соответствующего-высказывания), во­обще не являются алгоритмическими.

Таким образом, получается, что, если мы хотим встроить в систему все доступные человеку методы, позволяющие одно­значно установить, что те или иные вычисления действительно образуют петли, необходимо снабдить ее неким «невычислитель­ным интеллектом». Можно, конечно, предположить, что петель можно избежать с помощью некоего механизма, который бу­дет оценивать, как долго уже выполняется текущее вычисление, и «выскакивать из системы», если ему покажется, что оно вы­полняется слишком долго. Однако такой способ не сработает, если механизм, принимающий подобные решения, является по своей природе вычислительным, поскольку в этом случае неиз­бежны ситуации, когда упомянутый механизм со своей задачей не справляется, либо приходя к ошибочному заключению, что вычисление зациклилось, либо вообще не приходя ни к какому заключению (по той причине, что теперь зациклился уже сам ме­ханизм). Целиком и полностью вычислительной системе нечего противопоставить проблеме образования петель, и нет никаких гарантий, что вся система в целом, пусть даже избежав ошибоч­ных выводов, в конце концов не зациклится.

А что если ввести в процесс принятия решения о необхо­димости «выскакивать из системы» (в случае предположительно зациклившегося вычисления) и о том, когда именно это нужно делать, некоторые случайные элементы? Как мы отмечали выше (в частности, в §3.18), от чисто случайных элементов — в проти­воположность вычислительным псевдослучайным — нам в этой связи никакой реальной пользы не будет. Кроме того, если мы действительно хотим знать точно, образует ли петлю то или иное вычисление (т. е. истинно ли соответствующее-высказыва­ние), то следует учесть еще один момент. Сами по себе случайные процедуры не годятся для решения таких задач, поскольку, исхо­дя из самой природы феномена, называемого нами случайностью, о выводах, действительно обусловленных случайными элемента­ми, определенно можно сказать лишь одно — какая бы то ни было определенность в них напрочь отсутствует. Известны, одна­ко, вычислительные процедуры со случайными (или псевдослу­чайными) элементами, позволяющие получить математический результат с очень высокой степенью достоверности. Существу­ют, например, весьма эффективные методы со случайным вхо­дящим потоком, позволяющие определить, является ли данное большое число простым, причем практически в любом конкрет­ном случае результат оказывается правильным. Математически строгие методы проверки гораздо менее эффективны — поневоле задумаешься, что же предпочтительнее: сложное, но математи­чески точное построение, которое, не исключено, содержит не одну ошибку, или относительно простое, но вероятностное рассу­ждение, вероятность ошибки в котором на практике может ока­заться значительно меньше, нежели в первом случае. Подобные размышления порождают множество неловких вопросов, ломать копья из-за которых я не испытываю ни малейшего желания. Достаточно будет сказать, что для «принципиальных» рассужде­ний, которым посвящена большая часть этой главы, вероятност­ное доказательство, с помощью которого можно устанавливать истинность-высказываний, неизбежно оказывается, скажем так, не совсем адекватным.

Если мы намерены научиться однозначно устанавливать ис­тинность любого-высказывания в принципе, то, вместо то­го, чтобы бездумно полагаться на случайные или непознавае­мые процедуры, нам необходимо достичь подлинного понима­ния смысла феноменов, с этими высказываниями действитель­но связанных. Возможно, процедуры, полученные методом проб и ошибок, и дадут нам некоторые указания относительно то­го, где искать необходимые сведения, однако сами по себе та­кие процедуры окончательными критериями истинности являться не могут.

В качестве примера вернемся к вычислению, приведенно­му в комментарии к возражению(§2.6): «распечатать по­следовательность изединиц, после чего остановиться». Если просто выполнять это вычисление в точном соответствии с данными инструкциями, то его никоим образом невозможно будет завершить, даже если каждый отдельный его шаг будет занимать наименьший возможный с точки зрения теоретической физики промежуток времени (околос) — на его выпол­нение потребуется срок, невообразимо больший нынешнего воз­раста Вселенной (или достижимого ею в любом обозримом бу­дущем). И все же это вычисление весьма просто описать (осо­бенно если припомнить, что), причем абсолютно очевидно, что в конечном итоге оно все равно завершится. Ес­ли же мы вознамеримся счесть, что вычисление зациклилось на том только основании, что оно якобы «выполняется слишком долго», каким безнадежно далеким от истины окажется такое предположение!

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

В 1769 году Эйлер предположил, что это вычисление является незавершаемым. В середине 1960-х Л.Лэндером и Т. Паркином была предпринята попытка отыскать решение с помощью специ­ально разработанной компьютерной программы (см. [233]), одна­ко проект через некоторое время оставили ввиду отсутствия пер­спективы получить искомое решение в сколько-нибудь обозри­мом будущем — получаемые в процессе числа оказались слиш­ком велики для имеющегося в распоряжении математиков ком­пьютера, и они просто-напросто сдались. По всему выходило, что это вычисление и впрямь не завершается. Однако в 1987 году математику (человеку, кстати) Ноаму Элькису не только удалось показать, что решение таки существует, но и представить его в численном виде: ,,иОн также показал, что существует бесконечно много других решений, существенно отличных от полученного им. Воодушевленный этим результатом Роджер Фрай решил возоб­новить компьютерный поиск, внеся в программу несколько пред­ложенных Элькисом упрощающих поправок и, в конечном счете, затратив приблизительно 100 часов компьютерного времени, по­лучил несколько, правда, меньшее (вообще говоря, наименьшее возможное), но вполне подходящее решение:, ,и

Лавры за решение этой задачи следует разделить поровну между математическими интуитивными прозрениями и прямы­ми вычислительными подходами. Решая задачу математически, Элькис прибегал и к помощи компьютерных вычислений, пусть и относительно несущественных, хотя по большей своей части его аргументация таких подпорок не требует. И наоборот, как мы видели выше, для того чтобы сделать вычисление вообще воз­можным, Фраю потребовалось весьма существенная помощь со стороны человеческой интуиции.

Думаю, следует поместить нашу задачу в несколько более подробный контекст — первоначальное предположение Эйлера, сделанное в 1769 году, представляло собой нечто вроде обоб­щения знаменитой «последней теоремы Ферма», согласно ко­торой, как читатель, возможно, припоминает, верно следующее:

уравнение

не имеет решения в положительных целых числахесли n больше 2 (см., напр., [88]9). Мы можем перефразировать предположение Эйлера и записать его в следующем виде: не име­ет решения в положительных целых числах уравнение

гдесуть положительные целые числа общим количеством, аравно 4 или больше. Утверждение Ферма относится к случаю(частный случай предположения Эйлера, причем то, что соответствующее уравнение решений не имеет, сам Ферма и доказал — вот только доказательства нам не оставил). Прошло почти 200 лет, прежде чем был найден первый пример, опровергающий предположение Эйлера (в случае), - для отыскания решения был использован компьютерный перебор (подробнее об этом можно прочесть в той же статье Лэндера и Паркина, на которую я уже ссылался выше и в которой сообща­ется о неудаче со случаем):

Вспомним еще об одном знаменитом примере вычисления, о котором известно лишь то, что оно в конце концов завершает­ся; когда именно оно завершается, неизвестно до сих пор. Это вычисление связано с задачей об отыскании точки, в которой одна хорошо известная приближенная формула для определения количества простых чисел, меньших некоторого положительно­го целого n (интегральный логарифм Гаусса), оказывается не в состоянии это количество оценить. В 1914 году Дж. Э. Литлвуд показал, что в некоторой точке эта задача имеет решение. (При­близительно то же можно выразить и иначе: например, доподлин­но известно, что две кривые в некоторой точке пересекаются.)

В 1935 году ученик Литлвуда по фамилии Скьюс показал, что упомянутая точка приходится на число, меньшее, однако точное число так и остается неизвестным, хотя оно, конечно же, значительно меньше предела, поставленного Скьюсом. (Это число называли в свое время «наибольшим число, когда-либо естественным образом возникавшим в математике», однако тот временный рекорд оказался на настоящий момент побит с огром­ным отрывом в примере, приведенном в работе Грэма и Ротшиль­да [164], с. 290.)

Попробую осветить полученный вывод под несколько иным углом зрения. Предположим, что, пытаясь обойти налагаемые теоремой Гёделя ограничения, некто решил построить такого ро­бота, который будет способен каким-либо образом «выскакивать из системы» всякий раз, когда управляющий им алгоритм попадет в вычислительную петлю. В конце концов именно постоянное приложение теоремы Гёделя не позволяет нам спокойно при­нять предположение о том, что математическое понимание можно объяснить посредством вычислительных процедур, поэтому, как мне кажется, стоит рассмотреть с этой точки зрения трудности, с которыми сталкивается любая вычислительная модель матема­тического понимания при встрече с теоремой Гёделя.

Мне кто-то говорил, что где-то живут ящерицы, тупость ко­торых настолько велика, что они, подобно «обычным компьюте­рам и некоторым насекомым», способны «зацикливаться». Если несколько таких ящериц поместить на край круглого блюда, то они в вечной «гонке за лидером» будут бегать по кругу до тех пор, пока не умрут от истощения. Смысл этой истории в том, что подлинно интеллектуальная система должна располагать какими-то средствами для разрыва таких петель, тогда как ни один из существующих компьютеров подобными качествами, вообще го­воря, не обладает. (Проблему «разрыва петель» рассматривал Хофштадтерв[200].)

Вычислительная петля простейшего типа возникает, когда система на некотором этапе своей работы возвращается назад, в точности в то же состояние, в каком она пребывала на некотором предыдущем этапе. В отсутствие ввода каких-то дополнитель­ных данных она будет просто повторять одно и то же вычис­ление бесконечно. Не составляет большой трудности построить систему, которая, в принципе, будет гарантированно (пусть и не слишком эффективно) выбираться из петель подобного рода по мере их возникновения (скажем, посредством ведения списка всех состояний, в которых оказывается система, и проверки на каждом этапе на предмет выяснения, не встречалось ли такое состояние когда-либо раньше). Существует, однако, множество других возможных типов петель, причем гораздо более слож­ных. Собственно говоря, проблеме образования петель посвяще­на большая часть рассуждений главы 2 (в особенности, §§2.1 — 2.6), так как вычисление, застрявшее в петле, есть не что иное, как вычисление, которое не завершается. Собственно говоря, под  -высказыванием мы как раз и понимаем утверждение о том, что некоторое вычисление образует петлю (см. §2.10, коммен­тарий к возражению). А еще в § 2.5 мы имели возможность убедиться в том, что факт незавершаемости вычисления (т. е. об­разования петли) однозначно установить с помощью одних лишь алгоритмических методов невозможно. Более того, как можно заключить из вышеприведенных рассуждений, процедуры, по­средством которых математики-люди устанавливают, что данное конкретное вычисление действительно образует петлю (т. е. уста­навливают истинность соответствующего-высказывания), во­обще не являются алгоритмическими.

Таким образом, получается, что, если мы хотим встроить в систему все доступные человеку методы, позволяющие одно­значно установить, что те или иные вычисления действительно образуют петли, необходимо снабдить ее неким «невычислитель­ным интеллектом». Можно, конечно, предположить, что петель можно избежать с помощью некоего механизма, который бу­дет оценивать, как долго уже выполняется текущее вычисление, и «выскакивать из системы», если ему покажется, что оно вы­полняется слишком долго. Однако такой способ не сработает, если механизм, принимающий подобные решения, является по своей природе вычислительным, поскольку в этом случае неиз­бежны ситуации, когда упомянутый механизм со своей задачей не справляется, либо приходя к ошибочному заключению, что вычисление зациклилось, либо вообще не приходя ни к какому заключению (по той причине, что теперь зациклился уже сам ме­ханизм). Целиком и полностью вычислительной системе нечего противопоставить проблеме образования петель, и нет никаких гарантий, что вся система в целом, пусть даже избежав ошибоч­ных выводов, в конце концов не зациклится.

А что если ввести в процесс принятия решения о необхо­димости «выскакивать из системы» (в случае предположительно зациклившегося вычисления) и о том, когда именно это нужно делать, некоторые случайные элементы? Как мы отмечали выше (в частности, в §3.18), от чисто случайных элементов — в проти­воположность вычислительным псевдослучайным — нам в этой связи никакой реальной пользы не будет. Кроме того, если мы действительно хотим знать точно, образует ли петлю то или иное вычисление (т. е. истинно ли соответствующее-высказыва­ние), то следует учесть еще один момент. Сами по себе случайные процедуры не годятся для решения таких задач, поскольку, исхо­дя из самой природы феномена, называемого нами случайностью, о выводах, действительно обусловленных случайными элемента­ми, определенно можно сказать лишь одно — какая бы то ни было определенность в них напрочь отсутствует. Известны, одна­ко, вычислительные процедуры со случайными (или псевдослу­чайными) элементами, позволяющие получить математический результат с очень высокой степенью достоверности. Существу­ют, например, весьма эффективные методы со случайным вхо­дящим потоком, позволяющие определить, является ли данное большое число простым, причем практически в любом конкрет­ном случае результат оказывается правильным. Математически строгие методы проверки гораздо менее эффективны — поневоле задумаешься, что же предпочтительнее: сложное, но математи­чески точное построение, которое, не исключено, содержит не одну ошибку, или относительно простое, но вероятностное рассу­ждение, вероятность ошибки в котором на практике может ока­заться значительно меньше, нежели в первом случае. Подобные размышления порождают множество неловких вопросов, ломать копья из-за которых я не испытываю ни малейшего желания. Достаточно будет сказать, что для «принципиальных» рассужде­ний, которым посвящена большая часть этой главы, вероятност­ное доказательство, с помощью которого можно устанавливать истинность-высказываний, неизбежно оказывается, скажем так, не совсем адекватным.

Если мы намерены научиться однозначно устанавливать ис­тинность любого-высказывания в принципе, то, вместо то­го, чтобы бездумно полагаться на случайные или непознавае­мые процедуры, нам необходимо достичь подлинного понима­ния смысла феноменов, с этими высказываниями действитель­но связанных. Возможно, процедуры, полученные методом проб и ошибок, и дадут нам некоторые указания относительно то­го, где искать необходимые сведения, однако сами по себе та­кие процедуры окончательными критериями истинности являться не могут.

В качестве примера вернемся к вычислению, приведенно­му в комментарии к возражению(§2.6): «распечатать по­следовательность изединиц, после чего остановиться». Если просто выполнять это вычисление в точном соответствии с данными инструкциями, то его никоим образом невозможно будет завершить, даже если каждый отдельный его шаг будет занимать наименьший возможный с точки зрения теоретической физики промежуток времени (околос) — на его выпол­нение потребуется срок, невообразимо больший нынешнего воз­раста Вселенной (или достижимого ею в любом обозримом бу­дущем). И все же это вычисление весьма просто описать (осо­бенно если припомнить, что), причем абсолютно очевидно, что в конечном итоге оно все равно завершится. Ес­ли же мы вознамеримся счесть, что вычисление зациклилось на том только основании, что оно якобы «выполняется слишком долго», каким безнадежно далеким от истины окажется такое предположение!

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

В 1769 году Эйлер предположил, что это вычисление является незавершаемым. В середине 1960-х Л.Лэндером и Т. Паркином была предпринята попытка отыскать решение с помощью специ­ально разработанной компьютерной программы (см. [233]), одна­ко проект через некоторое время оставили ввиду отсутствия пер­спективы получить искомое решение в сколько-нибудь обозри­мом будущем — получаемые в процессе числа оказались слиш­ком велики для имеющегося в распоряжении математиков ком­пьютера, и они просто-напросто сдались. По всему выходило, что это вычисление и впрямь не завершается. Однако в 1987 году математику (человеку, кстати) Ноаму Элькису не только удалось показать, что решение таки существует, но и представить его в численном виде: ,,иОн также показал, что существует бесконечно много других решений, существенно отличных от полученного им. Воодушевленный этим результатом Роджер Фрай решил возоб­новить компьютерный поиск, внеся в программу несколько пред­ложенных Элькисом упрощающих поправок и, в конечном счете, затратив приблизительно 100 часов компьютерного времени, по­лучил несколько, правда, меньшее (вообще говоря, наименьшее возможное), но вполне подходящее решение:, ,и

Лавры за решение этой задачи следует разделить поровну между математическими интуитивными прозрениями и прямы­ми вычислительными подходами. Решая задачу математически, Элькис прибегал и к помощи компьютерных вычислений, пусть и относительно несущественных, хотя по большей своей части его аргументация таких подпорок не требует. И наоборот, как мы видели выше, для того чтобы сделать вычисление вообще воз­можным, Фраю потребовалось весьма существенная помощь со стороны человеческой интуиции.

Думаю, следует поместить нашу задачу в несколько более подробный контекст — первоначальное предположение Эйлера, сделанное в 1769 году, представляло собой нечто вроде обоб­щения знаменитой «последней теоремы Ферма», согласно ко­торой, как читатель, возможно, припоминает, верно следующее:

уравнение

не имеет решения в положительных целых числахесли n больше 2 (см., напр., [88]9). Мы можем перефразировать предположение Эйлера и записать его в следующем виде: не име­ет решения в положительных целых числах уравнение

гдесуть положительные целые числа общим количеством, аравно 4 или больше. Утверждение Ферма относится к случаю(частный случай предположения Эйлера, причем то, что соответствующее уравнение решений не имеет, сам Ферма и доказал — вот только доказательства нам не оставил). Прошло почти 200 лет, прежде чем был найден первый пример, опровергающий предположение Эйлера (в случае), - для отыскания решения был использован компьютерный перебор (подробнее об этом можно прочесть в той же статье Лэндера и Паркина, на которую я уже ссылался выше и в которой сообща­ется о неудаче со случаем):

Вспомним еще об одном знаменитом примере вычисления, о котором известно лишь то, что оно в конце концов завершает­ся; когда именно оно завершается, неизвестно до сих пор. Это вычисление связано с задачей об отыскании точки, в которой одна хорошо известная приближенная формула для определения количества простых чисел, меньших некоторого положительно­го целого n (интегральный логарифм Гаусса), оказывается не в состоянии это количество оценить. В 1914 году Дж. Э. Литлвуд показал, что в некоторой точке эта задача имеет решение. (При­близительно то же можно выразить и иначе: например, доподлин­но известно, что две кривые в некоторой точке пересекаются.)

В 1935 году ученик Литлвуда по фамилии Скьюс показал, что упомянутая точка приходится на число, меньшее, однако точное число так и остается неизвестным, хотя оно, конечно же, значительно меньше предела, поставленного Скьюсом. (Это число называли в свое время «наибольшим число, когда-либо естественным образом возникавшим в математике», однако тот временный рекорд оказался на настоящий момент побит с огром­ным отрывом в примере, приведенном в работе Грэма и Ротшиль­да [164], с. 290.)