Утверждение  вполне способно потрясти воображение и не слишком впечатлительного читателя, особенно если учесть достаточно простой характер составных элементов рассуждения, из которого мы это утверждение вывели. Прежде чем перейти к рас­смотрению (в главе 3) его следствий применительно к возмож­ности создания разумного робота-математика с компьютерным разумом, необходимо очень тщательно исследовать некоторое количество формальных моментов, связанных с получением вы­вода ^'. Если подобные возможные формальные «лазейки» вас не смущают и вы готовы принять на веру утверждение У (согласно которому, напомним, математики при установлении математиче­ской истины не применяют заведомо обоснованные алгоритмы), то вы, вероятно, предпочтете пропустить (или хотя бы на неко­торое время отложить) нижеследующие рассуждения и перейти непосредственно к главе 3. Более того, если вы готовы принять на веру и несколько более серьезный вывод, в соответствии с кото­рым принципиально невозможно алгоритмически объяснить ни математическое, ни какое-либо иное понимание, то вам, возмож­но, стоит перейти сразу ко второй части книги — задержавшись разве что на воображаемом диалоге в §3.23 (обобщающем наи­более важные аргументы главы 3) и выводах в § 3.28.

Существует несколько математических моментов, связан­ных с приведенным в §2.5 гёделевским доказательством, кото­рые не дают людям покоя. Попытаемся с этими моментами разо­браться.

Q1. Я  понимаю так,  что  процедура А является единичной, тогда как во всевозможных математи­ческих обоснованиях мы, несомненно, применяем много разных способов рассуждения. Не следует ли нам принять во внимание возможность существования целого ряда возможных «процедур А»?

В действительности, использование мною такой формули­ровки вовсе не влечет за собой потери общего характера рас­суждений в целом. Любой конечный ряд ai, Ау, аз, ..., Аг ал­горитмических процедур всегда можно выразить в виде единич­ного алгоритма А, причем таким образом, что А окажется неза­вершаемым только в том случае, если не завершаются все от­дельные алгоритмы ai, ..., Ат. (Процедура А может протекать, например, следующим образом: «Выполнить первые 10 шагов алгоритма А\, запомнить результат; выполнить первые 10 шагов алгоритма А^\ запомнить результат; выполнить первые 10 шагов алгоритма аз', запомнить результат; и так далее вплоть до Аг затем вернуться к А\ и выполнить следующие 10 шагов; запо­мнить результат и т. д.; затем перейти к третьей группе из 10 ша­гов и т. п. Завершить процедуру, как только завершится любой из алгоритмов Д.».) Если же ряд алгоритмов А бесконечен, то для того, чтобы его можно было считать алгоритмической про­цедурой, необходимо найти способ порождения всей совокупно­сти алгоритмов ai, А-2, А3, ... алгоритмическим путем. Тогда мы сможем получить единичный алгоритм А, который заменяет весь ряд алгоритмов и выглядит приблизительно следующим образом:

«первые 10 этапов-A1;

вторые 10 этаповА1, первые 10 этаповА2;

третьи 10 этапов A1, вторые 10 этаповА2, первые 10 этаповА3;

… и т.д.»…

Завершается такой алгоритм лишь после успешного завершения любого алгоритма из ряда, и никак не раньше.

С другой стороны, можно представить себе ситуацию, когда ряд a1, a2, аз,…, предположительно бесконечный, заранее не задан даже в принципе. Время от времени к такому ряду добавля­ется следующая алгоритмическая процедура, однако изначально весь ряд в целом не определен. В этом случае, ввиду отсутствия какой-либо предварительно заданной алгоритмической процеду­ры для порождения такого ряда, единичный замкнутый алгоритм нам получить никак не удастся.

Q2. Мы, безусловно, должны допустить, что алгоритм А может оказаться и не фиксированным. Лю­ди, в конце концов, обладают способностью к обучению, а значит, применяемый ими при этом алгоритм вполне может претерпевать непрерывные из­менения.

Для описания изменяющегося алгоритма необходимо каким-то образом задать правила, согласно которым он, собственно, изменяется. Если сами по себе эти правила являются полностью алгоритмическими, то мы уже включили их в описание нашей гипотетической процедуры «А», иначе говоря, такой «изменя­ющийся алгоритм» на деле представляет собой всего-навсего еще один пример единичного алгоритма, и на наши рассужде­ния подобное допущение никак не влияет. С другой стороны, можно вообразить средства для изменения алгоритма, предпо­ложительно не являющиеся алгоритмическими: такие, например, как введение в алгоритм каких-то случайных составляющих или неких процедур взаимодействия его с окружением. «Неалгорит­мический» статус подобных средств изменения алгоритма мы еще будем рассматривать несколько позднее (см. §§ 3.9, 3.10); можно также вернуться к § 1.9, где было показано, что ни одно из этих средств не позволяет сколько-нибудь убедительно избавиться от алгоритмизма (как того требует точка зрения ^). В данном слу­чае, т. е. в рамках чисто математических рассуждений, нас зани­мает лишь возможность того, что такое изменение действительно будет носить алгоритмический характер. Если же предположить, что алгоритмическим оно быть никак не может, то мы, без­условно, придем к полному согласию с выводом &.

Пожалуй, следует немного подробнее остановиться на том, что может обозначать определение «алгоритмически изменяю­щийся» применительно к алгоритму А. Допустим, что алгоритм А зависит не только от q и п, но и еще от одного параметра t, который можно рассматривать как «время», а можно как просто количество предшествующих настоящему моменту случаев ак­тивации нашего алгоритма. Как бы то ни было, мы можем так­же предположить, что параметр t является натуральным числом, и записать следующий ряд алгоритмов At (<J, n):

A0(q,n), Ai(q,n), A2(q,n), A3(q, n), ..., каждый элемент которого предположительно является обосно­ванной процедурой для установления незавершаемости вычисле­ния Cq (n), при этом мы будем считать, что мощность этих проце­дур возрастает по мере увеличения t. Предполагается также, что способ, посредством которого увеличивается мощность этих про­цедур, является алгоритмическим. Возможно, этот «алгоритми­ческий способ» зависит некоторым образом от «опыта» выпол­нения предыдущих алгоритмов At (q, n), однако в данном случае мы предполагаем, что этот «опыт» порождается также алгорит­мически (в противном случае мы снова приходим к согласию с ), т.е. мы имеем полное право включить «опыт» (или способы его порождения) в перечень операций, составляющих следующий ал­горитм (т.е., собственно, в At (q. n)). Действуя таким образом, мы опять-таки получаем единичный алгоритм (At (q, n)), кото­рый зависит алгоритмически от всех трех параметров: t, q, п. На его основе можно построить алгоритм Л*, столь же мощный, что и весь ряд At (q, п), однако зависящий только от двух натуральных чисел: q и п. Для получения такого A* (q, n) нам, как и преж­де, необходимо лишь выполнить первые десять шагов алгорит­ма ао (q, n) и запомнить результат; затем первые десять шагов алгоритма А1 (q, n) и вторые десять шагов алгоритма ао (q, n), запоминая получаемые результаты; затем первые десять шагов алгоритма A2 (q, n), вторые десять шагов алгоритма А1(q, n), третьи десять шагов алгоритма A0 (q, n) и т. д., "запоминая по­лучаемые на каждом шаге вычисления результаты. В конечном итоге, сразу после завершения любого из составляющих алго­ритм вычислений завершается выполнение и всей процедуры в целом. Замена процедуры А процедурой А* никак не влияет на ход рассуждений, посредством которых мы пришли к выводу .

Q3. Не был ли я излишне категоричен, утверждая, что в тех случаях, когда уже можно определенно утверждать, что данное вычисление Сq(п) и вправду завершается, алгоритм А все равно должен вы­полняться бесконечно? Допусти мы, что А в таких случаях также завершается, все наше рассужде­ние оказалось бы ложным. В конце концов, обще­известно, что присущая людям способность к ин­туитивному пониманию позволяет им порой делать заключение о возможности завершения того или иного вычисления, однако я, судя по всему, здесь этой способностью пренебрег. Не слишком ли мно­го искусственных ограничений?

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

Если вас такое положение дел не устраивает, попробуйте представить алгоритм А следующим образом: пусть А объединя­ет в себе оба вида понимания, но в том случае, когда выясняется, что вычисление Cq(n) действительно завершается, алгоритм А искусственно зацикливается (т. е. выполняет какую-то операцию снова и снова, бесконечное количество раз). Разумеется, на са­мом деле математики работают иначе, однако дело не в этом. Наше рассуждение построено как redactio ad absurdum, т.е. начав с допущения, что для установления математической исти­ны используются заведомо обоснованные алгоритмы, мы в итоге приходим к противоположному выводу. Такое доказательство не требует, чтобы гипотетическим алгоритмом непременно оказался какой-то конкретный алгоритм А, мы вполне можем заменить его на другой алгоритм, построенный на основе А, — как, например, в только что упомянутом случае.

Этот комментарий применим и к любому другому возраже­нию вида: «А что если алгоритм А завершится по какой-либо совершенно посторонней причине и не даст нам доказательства того, что вычисление Cq (n) не завершается?». Если нам вдруг придется иметь дело с алгоритмом «Л», который ведет себя по­добным образом, то мы просто применим представленное в §2.5 обоснование к немного другому А — а именно, к такому, который зацикливается всякий раз, когда исходный «Л» завершается по любой из упомянутых посторонних причин.

Q4. Судя по всему, каждое вычисление Cq в пред­ложенной мною последовательности С0, С1, С2,… является вполне определенным, тогда как при лю­бом прямом переборе (численном или алфавит­ном) компьютерных программ ситуация, конечно же, была бы иной?

В самом деле, было бы весьма затруднительно однознач­но гарантировать, что каждому натуральному числу q в нашей последовательности действительно соответствует некое рабочее вычисление Cq. Например, описанная в НРК последователь­ность машин Тьюринга Тд этому условию, конечно же, не удовле­творяет; см. НРК, с. 54. При определенных значениях q маши­ну Тьюринга Tq можно назвать «фиктивной» по одной из четырех причин: ее работа никогда не завершается; она оказывается «некорректно определенной», поскольку представление числа n в виде двоичной последовательности содержит слишком много (пять или более) единиц подряд и, как следствие, не имеет интер­претации в данной схеме; она получает команду, которая вводит ее в нигде не описанное внутреннее состояние; или же по за­вершении работы она оставляет ленту пустой, т. е. не дает ника­кого численно интерпретируемого результата. (См. также При­ложение А.) Для приведенного в §2.5 доказательства Гёделя-Тьюринга вполне достаточно объединить все эти причины в одну категорию под названием «вычисление не завершается». В част­ности, когда я говорю, что вычислительная процедура А «завер­шается» (см. также примечание на с. 122), я подразумеваю, что она «завершается» как раз в вышеупомянутом смысле (а пото­му не содержит неинтерпретируемых последовательностей и не оставляет ленту пустой), — иными словами, «завершиться» мо­жет только действительно корректно определенное рабочее вы­числение. Аналогично, фраза «вычисление Cq (n) завершается» означает, что данное вычисление корректно завершается именно в этом смысле. При такой интерпретации соображение Q4 не имеет совершенно никакого отношения к представленному мною доказательству.

Q5. Не является ли мое рассуждение лишь демонстрацией неприменимости некоей частной алго­ритмической процедуры (А) к выполнению вычис­ления Cq (n)? И каким образом оно показывает, что я справлюсь с задачей лучше, чем какая бы то ни было процедура A?

Оно и в самом деле вполне однозначно показывает, что мы справляемся с такого рода задачами гораздо лучше любого ал­горитма. Поэтому, собственно, я и воспользовался в своем рас­суждении приемом reductio ad absurdum. Пожалуй, в данном случае уместно будет привести аналогию. Читателям, вероятно, известно о евклидовом доказательстве невозможности отыскать наибольшее простое число, также основанном на reductio ad absurdum. Доказательство Евклида выглядит следующим обра­зом. Допустим, напротив, что такое наибольшее простое число нам известно; назовем его р. Теперь рассмотрим число N, кото­рое представляет собой сумму произведения всех простых чисел вплоть до р и единицы:

N = 2*3*5* ... * р + 1.

Число N, безусловно, больше р, однако оно не делится ни на одно из простых чисел 2, 3, 5, ..., р (поскольку при делении получаем единицу в остатке), откуда следует, что N либо и есть искомое наибольшее простое число, либо оно является составным, и тогда его можно разделить на простое число, большее р. И в том, и в другом случае мы находим простое число, большее р, что проти­воречит исходному допущению, заключавшемуся в том, что р есть наибольшее простое число. Следовательно, наибольшее простое число отыскать нельзя.

Такое рассуждение, основываясь на reductio ad absurdum, не просто показывает, что требуемому условию не соответству­ет некое частное простое число р, поскольку можно отыскать число больше него; оно показывает, что наибольшего простого числа просто не может существовать в природе. Аналогично, представленное выше доказательство Гёделя—Тьюринга не про­сто показывает, что нам не подходит тот или иной частный алго­ритм А, оно демонстрирует, что в природе не существует алго­ритма (познаваемо обоснованного), который был бы эквивален­тен способности человека к интуитивному пониманию, которую мы применяем для установления факта незавершаемости тех или иных вычислений.

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

Отыскание конкретного вычисления Ck (k) при заданном алгоритме А, безусловно, представляет собой вычислительный процесс. Более того, это можно достаточно явно показать. Означает ли это, что предположительно неалгоритмическая математи­ческая интуиция — интуиция, благодаря которой мы определяем, что вычисление Ck (k) никогда не завершается — на деле явля­ется все же алгоритмической?

Думаю, данное суждение следует рассмотреть более подроб­но, поскольку оно представляет собой одно из наиболее рас­пространенных недоразумений, связанных с гёделевским доказа­тельством. Следует особо уяснить, что оно не сводит на нет ничего из сказанного ранее. Хотя процедуру отыскания вычис­ления Ck (k) с помощью алгоритма А можно представить в виде вычисления, это вычисление не входит в перечень процедур, со­держащихся в Л. И не может входить, поскольку самостоятель­но алгоритм А не способен установить истинность Ck (k), тогда как новое вычисление (вкупе с А], судя по всему, вполне на это способно. Таким образом, несмотря на то, что с помощью нового вычисления действительно можно отыскать вычисление Ck (k), членом клуба «официальных установителей истины» оно не яв­ляется.

Изложим все это несколько иначе. Вообразите себе управ­ляемого компьютером робота, способного устанавливать мате­матические истины с помощью алгоритмических процедур, со­держащихся в А. Для большей наглядности я буду пользоваться антропоморфной терминологией и говорить, что робот «знает» те математические истины (в данном случае — связанные с установ­лением факта незавершаемости вычислений), которые он может вывести, применяя алгоритм А. Однако если наш робот «знает» лишь А, то он никак не сможет «узнать», что вычисление Ck (k) не завершается, даже если процедура отыскания Ck (k) с по­мощью А является целиком и полностью алгоритмической. Мы, разумеется, могли бы сообщить роботу о том, что вычисле­ние Ck (k} и в самом деле не завершается (воспользовавшись для установления этого факта собственными пониманием и ин­туицией), однако, если робот примет это утверждение на «веру», ему придется изменить свои собственные правила, присоединив полученную новую истину к тем, что он уже «знает». Мы можем пойти еще дальше и каким-либо способом сообщить нашему ро­боту о том, что для получения новых истин на основании старых ему, помимо прочего, необходимо «знать» и общую вычислитель­ную процедуру отыскания Ck (k) посредством алгоритма А. К запасу «знаний» робота можно добавить все, что является вполне определенным и вычислительным по своей природе. Однако в ре­зультате у нас появляется новый алгоритм «Л», и доказательство Гёделя следует применять уже к нему, а не к старому А. Иначе говоря, везде вместо старого А нам следовало бы использовать новый «Л», поскольку менять алгоритм «Л» посреди доказатель­ства есть не что иное, как жульничество. Таким образом, как мы видим, изъян возражения Q6 очень похож на рассмотренный выше изъян Q5. В нашем reductio ad absurdum мы полагаем, что алгоритм А (под которым понимается некая познаваемая и обоснованная процедура для установления факта незавершаемости вычислений) в действительности представляет собой всю совокупность известных математикам подобных процедур, из чего и следует противоречие. Попытку введения еще одной вы­числительной процедуры для установления истины — процеду­ры, не содержащейся в А, — после того как мы договорились, что А представляет собой всю их совокупность, я расцениваю как жульничество.

Беда нашего злосчастного робота в том, что, не обладая ка­ким бы то ни было пониманием гёделевской процедуры, он не располагает ни одним надежным и независимым способом уста­новления истины — истину ему сообщаем мы. (Эта проблема, вообще говоря, не имеет никакого отношения к вычислитель­ным аспектам доказательства Гёделя.) Для того чтобы достичь чего-то большего, ему, как и всем нам, необходимо понимание смысла операций, которые ему велено выполнять. Если тако­го понимания нет, то он вполне может «знать» (ошибочно), что вычисление Ck (k} завершается, а вовсе не наоборот. Заклю­чение (ошибочное) «вычисление Ck (&) завершается» выводится точно так же алгоритмически, как и заключение (правильное) «вычисление Ck (k) не завершается». Таким образом, дело во­все не в алгоритмическом характере этих операций, а в том, что для различения между алгоритмами, приводящими к истинным заключениям, и теми, что приводят к заключениям ложным, наш робот нуждается в способности выносить достоверные сужде­ния об истинности. Далее, на данной стадии рассуждения, мы все еще допускаем возможность того, что процесс «понимания» представляет собой некую разновидность алгоритмической дея­тельности, которая не содержится ни в одной из точно заданных и «заведомо» обоснованных процедур типа А. Например, пони­мание может осуществляться посредством выполнения какого-то необоснованного или непознаваемого алгоритма. В дальнейшем (см. главу 3) я попробую убедить читателя в том, что в действи­тельности понимание вообще не является алгоритмической дея­тельностью. На настоящий же момент нас интересуют всего лишь строгие следствия из доказательства Гёделя—Тьюринга, а на них возможность получения вычисления С^ (k) из процедуры А вы­числительным путем никоим образом не влияет.

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

Несмотря на кажущуюся логичность этого утверждения, здесь упущен из виду один очень существенный момент, а именно: способ, посредством которого мы (или компьютеры) определяем, какие математические утверждения истинны, а какие — ложны. (Во всяком случае, на простое хранение математических утвер­ждений способны и системы, гораздо менее сложные, нежели универсальный компьютер — например, фотоаппараты.) Прин­цип использования компьютера в Q7 совершенно не учитывает критического вопроса о наличии у этого самого компьютера спо­собности суждения об истинности. С равным успехом мож­но вообразить и компьютеры, в памяти которых не содержится ничего, кроме перечня абсолютно ложных математических «тео­рем», либо случайным образом перемешанных истинных и лож­ных утверждений. Откуда мы узнаем, какому компьютеру можно доверять? Я отнюдь не утверждаю, что эффективное моделиро­вание результатов сознательной интеллектуальной деятельности человека (в данном случае, в области математики) абсолютно невозможно, поскольку по одной лишь чистой случайности ком­пьютер может «умудриться» сделать все правильно, пусть и не обладая каким бы то ни было пониманием. Однако шансы на это до абсурдного малы, в то время как те вопросы, на которые мы здесь пытаемся найти ответ (например, каким таким образом мы определяем, что вот это математическое утверждение истинно, а вот это — ложно?), в возражении Q7 и вовсе не затрагиваются. С другой стороны, Q7 все же напоминает об одном более существенном соображении. Имеет ли непосредственное отно­шение к нашему исследованию обсуждение бесконечных струк­тур (всех натуральных чисел или всех вычислений), если учесть, что совокупность всех результатов, полученных на тот или иной момент времени всеми людьми и компьютерами, имеет конечную величину? В следующем комментарии мы рассмотрим этот без­условно важный вопрос отдельно.

Q8. Незавершающиеся вычисления суть идеализи­рованные математические конструкции, по опре­делению бесконечные. Вряд ли подобные вопросы могут иметь сколько-нибудь непосредственное от­ношение к изучению конечных физических объек­тов — таких, как компьютеры или мозг.

Все верно, рассуждая в идеализированном ключе о машинах Тьюринга, незавершающихся вычислениях и т. п., мы рассматри­вали бесконечные (потенциально) процессы, тогда как в случае людей или компьютеров нам приходится иметь дело с системами конечными. И, разумеется, применяя подобные идеализирован­ные доказательства к реальным и конечным физическим объек­там, следует быть готовыми к тому, что такая операция непре­менно окажется связанной с теми или иными ограничениями и оговорками. Однако, как выясняется, учет конечной природы ре­альных объектов не изменяет сколько-нибудь существенно сути доказательства Гёделя—Тьюринга. Нет ничего странного в том, что мы рассуждаем об идеализированных вычислениях, обосно­вываем те или иные умозаключения и выводим, математически, их теоретические ограничения. Можно, к примеру, обсуждать в аб­солютно конечных терминах вопрос о том, существует ли нечет­ное число, являющееся суммой двух четных чисел, или существу­ет ли натуральное число, не являющееся суммой четырех квад­ратов (как в приведенных выше задачах (С) и (В)), нисколько не смущаясь тем, что при рассмотрении этих вопросов мы неявно учитываем бесконечное множество всех натуральных чисел. Мы имеем полное право рассуждать о незавершающихся вычисле­ниях или машинах Тьюринга вообще, как о математических структурах, пусть и не в силах создать на практике бесконеч­но работающую машину Тьюринга. (Отметим, в частности, что действие машины Тьюринга, занятой поисками нечетного числа, являющегося суммой двух четных чисел, строго говоря, практи­чески реализовать невозможно, так как ее детали износятся го­раздо раньше, чем минет вечность.) Описание любого единичного вычисления (или действия машины Тьюринга) — задача вполне конечная, а вопрос о том, завершится ли в конечном итоге это вычисление, можно полагать вполне определенным. Сначала мы доводим до логического завершения теоретические рассуждения, связанные с теми или иными идеализированными вычислениями, и лишь затем пытаемся разглядеть, каким образом наши рассу­ждения применимы к конечным физическим системам — таким, как реально существующие компьютеры или люди.

Ограничения конечного характера могут быть обусловлены либо тем, что (i) описание конкретного рассматриваемого вы­числения оказывается слишком громоздким (т. е. число п в Сп или пара чисел q, n в Cq (n) оказываются слишком велики для того, чтобы их мог описать человек или реально существующий компьютер), либо тем, что (п) при внешней простоте описания вычисление, тем не менее, требует для своего выполнения чрез­мерно много времени, в результате чего может показаться, что оно не завершается вовсе, хотя теоретически данное вычисле­ние должно в конечном счете завершиться. На деле же, как мы вскоре убедимся, выясняется, что из этих двух условий сколько-нибудь существенное влияние на наши рассуждения оказыва­ет только (i), да и оно не так уж и велико. Незначительность фактора (ii), быть может, покажется вам удивительной. Суще­ствует множество относительно простых вычислений, которые в конечном счете завершаются, однако точки их завершения путем прямого вычисления не способен достичь ни один потенциально возможный компьютер. Рассмотрим, например, следующую задачу: «распечатать последовательность из 2^2^65536 единиц, после чего остановиться». (В §3.26 будут предложены еще несколько подобных примеров, гораздо более интересных с математической точки зрения.) Вопрос о завершаемости того или иного вычис­ления не следует решать путем прямого вычисления: этот метод зачастую оказывается крайне неэффективным.

Для того чтобы выяснить, каким образом ограничения (i) или (ii) могут повлиять на наши гёделевские рассуждения, пройдемся еще раз по соответствующим частям доказательства. В соответ­ствии с ограничением (i), вместо бесконечного ряда вычислений, мы располагаем рядом конечным:

, , , , ,…,

где предполагается, что число Q задает наиболее громоздкое вы­числение, какое способен выполнить наш компьютер или чело­век. В случае с человеком вышеприведенное утверждение можно счесть несколько туманным. Впрочем, в настоящий момент нас не особенно заботит точное определение числа Q. (Вопрос о туман­ности утверждений, касающихся человеческих способностей, бу­дет рассмотрен ниже, в комментарии к возражению Q13 в § 2.10.) Кроме того, можно предположить, что, попытавшись применить упомянутые вычисления к какому-то конкретному натуральному числу п, мы обнаружим, что значение п ограничено некоторой фиксированной величиной N, поскольку наш компьютер (или че­ловек) оказывается не способен работать с числами, превыша­ющими N. (Строго говоря, следует учесть и возможность того, что число N не является фиксированным, но зависит от того или иного конкретного вычисления Cq, т. е. N может зависеть от q. Однако этот факт не влияет на наши рассуждения сколько-нибудь существенным образом.)

Как и ранее, мы рассматриваем некий обоснованный ал­горитм A (q, n), завершение выполнения которого равносиль­но доказательству того, что вычисление Cq (n) не завершается. Несмотря на то, что, в соответствии с ограничением (i), рассмот­рению подлежат только значения q, не превышающие Q, и только те значения п, не превышающие N, мы, говоря об «обоснован­ности», в действительности имеем в виду, что алгоритм А должен быть обоснованным для всех значений q и п, независимо от их величины. (Таким образом, можно видеть, что правила, реализуе­мые в алгоритме А, являются точными математическими пра­вилами, в отличие от правил приближенных, работающих только в силу того или иного практического ограничения, налагаемого на «реально осуществимые» вычисления.) Более того, утверждая, что «вычисление Cq (n) не завершается», мы имеем в виду, что это вычисление действительно не завершается, а не то, что это вычисление просто-напросто оказывается слишком громоздким для того, чтобы его мог выполнить наш компьютер или человек,

как предусматривает ограничение (ii).

Вспомним, что утверждение (Н) гласит:

Если завершается вычисление А(а,п), то вычисление Cq (n) не завершается.

Принимая во внимание ограничение (ii), можно было бы предпо­ложить, что алгоритм А оказывается не слишком эффективен при установлении факта незавершаемости очередного вычисления, поскольку сам он состоит из большего количества шагов, чем способен выполнить компьютер или человек. Однако, как выяс­няется, для нашего доказательства этот факт не имеет никакого значения. Мы намерены отыскать некое вычисление A (k, k), ко­торое не завершается вообще. Для нас абсолютно неважно, что в некоторых других случаях, когда вычисление А действительно завершается, мы не можем об этом узнать, так как не в состоянии дождаться этого самого завершения.

Далее, как и в равенстве (J), мы вводим натуральное чис­ло k, при котором вычисление А (п, п) совпадает с вычислени­ем Ck (n) для всех n:

А(n,n) = Ck(n).

Следует, впрочем, рассмотреть еще предусматриваемую ограни­чением (i) возможность того, что упомянутое число k окажется больше Q. В случае какого-нибудь невообразимо сложного вы­числения А такая ситуация вполне возможна, однако только при условии, что это А уже начинает приближаться к верхней границе допустимой сложности (в смысле количества двоичных знаков в его описании в формате машины Тьюринга), с которой может работать наш компьютер или человек. Это обусловлено тем, что вычисление, получающее значение k из описания вычисления А (например, в формате машины Тьюринга), — вещь достаточно простая и может быть задана в явном виде (как уже было пока­зано в комментарии к Q6).

Вообще говоря, для того чтобы поставить в тупик алгоритм А, нам необходимо лишь вычисление Ck (k) — подставляя в (Н) равенство n = k, получаем утверждение (L):

Если завершается вычисление A(k, k), то вычисление Ck(k) не завершается.

Поскольку A (k, k) совпадает с Ck (k), наше доказательство по­казывает, что, хотя данное конкретное вычисление Ck (k) никогда не завершается, посредством алгоритма А мы этот факт устано­вить не в состоянии, даже если бы упомянутый алгоритм мог вы­полняться гораздо дольше любого предела, налагаемого на него в соответствии с ограничением (ii). Вычисление Ck (k) задается только введенным ранее числом k, и, при условии, что k не пре­вышает ни Q, ни N, это вычисление и в самом деле в состоянии выполнить наш компьютер или человек — в смысле, в состоянии начать. Довести его до завершения невозможно в любом случае, поскольку это вычисление просто-напросто не завершается!

А может ли число k оказаться больше Q или N? Такое воз­можно лишь в том случае, когда для описания А требуется так много знаков, что даже совсем небольшое увеличение их коли­чества выводит задачу за пределы возможностей нашего ком­пьютера или человека. При этом, поскольку мы знаем об об­основанности алгоритма А, мы знаем и о том, что рассматри­ваемое вычисление Ck(k) не завершается, даже если реальное выполнение этого вычисления представляет для нас проблему. Соображение (i), однако, предполагает и возможность того, что вычисление А окажется столь колоссально сложным, что одно лишь его описание вплотную приблизится к доступному вообра­жению человека пределу сложности, а сравнительно малое уве­личение количества составляющих его знаков даст в результате вычисление, превосходящее всякое человеческое понимание. Что бы мы о подобной возможности ни думали, я все же считаю, что любой столь впечатляющий набор реализуемых в нашем гипо­тетическом алгоритме А вычислительных правил окажется, вне всякого сомнения, настолько сложным, что мы не в состоянии будем наверняка знать, является ли он обоснованным, даже если нам будут точно известны все эти правила по отдельности. Таким образом, наше прежнее заключение остается в силе: при установлении математических истин мы не применяем познава­емо обоснованные наборы алгоритмических правил.

Не помешает несколько более подробно остановиться на сравнительно незначительном увеличении сложности, сопрово­ждающем переход от А к Ck(k). Помимо прочего, это существен­но поможет нам в нашем дальнейшем исследовании (в §§3.19 и 3.20). В Приложении А (с. 191) предложено явное описание вычисления Ck(k) в виде предписаний для машины Тьюринга, рассмотренных в НРК (глава 2). Согласно этим предписаниям, под обозначением Тт понимается «m-я машина Тьюринга». Для большего удобства и упрощения рассуждений здесь мы также будем пользоваться этим обозначением вместо «Сm», в част­ности, для определения степени, сложности вычислительной процедуры или отдельного вычисления. В соответствии с выше­сказанным, определим степень сложности  машины Тьюрин­га Тт как количество знаков в двоичном представлении числа т (см. НРК, с. 39); при этом степень сложности некоторого вы­числения Тт (п) определяется как большее из двух чисел  и v, где v — количество двоичных знаков в представлении числа п. Рассмотрим далее приведенное в Приложении А явное предпи­сание для составления вычисления Ck(k) на основании алгорит­ма А, заданного в упомянутых спецификациях машины Тьюринга. Полагая степень сложности А равной а, находим, что степень сложности явного вычисления Ck (k) не превышает числа а + 210 log2 (а + 336) — а это число, в свою очередь, оказывается лишь очень ненамного больше собственно а, да и то только тогда, когда число а очень велико.

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

ВЗГЛЯНУТЬ.

Q9. Точка зрения, известная как интуиционизм, не позволяет сделать вывод о непременной завершаемости  вычисления на определенном этапе на том лишь основании, что бесконечное продолжение этого вычисления приводит к противоречию; бытуют в математике и иные точки зрения сходного характера — например, «конструктивизм» и «финнтизм». Не окажется ли гёделевское доказательство спорным, будучи рассмотрено с этих позиций?

В своем гёделевском доказательстве (в частности, в утвер­ждении (М)) я использовал аргумент следующего вида: «Допу­щение о ложности X приводит к противоречию; следовательно, утверждение X истинно». Под «X» в данном случае следует по­нимать утверждение: «Вычисление Ck (k) не завершается». Это рассуждение относится к типу reductio ad absurdum; что же касается доказательства Гёделя в целом, то оно и в самом деле построено именно таким образом. Направление же в математике, называемое «интуиционизмом» (у истоков которого стоял гол­ландский математик Л. Э. Я. Брауэр; см. [222] и НРК, с. 113— 116), отрицает возможность построения обоснованного доказа­тельства на основе reductio ad absurdum. Интуиционизм возник приблизительно в 1912 году как реакция на некоторые сформи­ровавшиеся к концу девятнадцатого — началу двадцатого века математические тенденции, суть которых сводится к следующему: математический объект можно полагать «существующим» даже в тех случаях, когда нет никакой возможности этот объект так или иначе воплотить в действительности. А надо сказать, что слиш­ком вольное применение крайне расплывчатой концепции мате­матического существования и впрямь приводит порой к весь­ма неприятным противоречиям. Самый известный пример такого противоречия связан с парадоксальным «множеством всех мно­жеств, не являющихся членами самих себя» Бертрана Рассела. (Если множество Рассела является членом самого себя, то оно таковым не является; если же оно членом самого себя не явля­ется, то оно им, как ни странно, является! Подробнее см. §3.4 и НРК, с. 101.) Дабы противостоять общей тенденции, в рам­ках которой могут считаться «существующими» весьма вольно определенные математические объекты, интуиционисты полага­ют необоснованным математическое рассуждение, позволяющее делать вывод о существовании того или иного математического объекта на основании одной лишь противоречивости его несуще­ствования. Доказательство существования объекта посредством reductio ad absurdum не дает абсолютно никаких оснований по­лагать, что упомянутый объект действительно можно построить. Каким  же  образом  запрет на  применение  reductio  ad absurdum может повлиять на наше гёделевское доказательство? Вообще говоря, совсем не может, по той простой причине, что reductio ad absurdum мы применяем, если можно так выра­зиться, наоборот, то есть противоречие в нашем случае выво­дится из допущения, что нечто существует, а не из обратного допущения. С интуиционистской точки зрения все выглядит со­вершенно законно: мы заключаем, что объект не существует, на том основании, что противоречие возникает как раз из допуще­ния о существовании этого самого объекта. Предложенное мною гёделевское доказательство, по сути своей, является в интуицио­нистском смысле абсолютно приемлемым. (См. [222], с. 492.)

Аналогичные рассуждения применимы и ко всем прочим «конструктивистским» или «финитистским» направлениям в ма­тематике, о каких мне известно. Комментарий к возражению Q8 демонстрирует, что даже та точка зрения, согласно которой по­следовательность натуральных чисел нельзя считать «на самом деле» бесконечной, не освобождает нас от неизбежного вывода: для установления математической истины мы таки не пользуемся познаваемо обоснованными алгоритмами.

Утверждение  вполне способно потрясти воображение и не слишком впечатлительного читателя, особенно если учесть достаточно простой характер составных элементов рассуждения, из которого мы это утверждение вывели. Прежде чем перейти к рас­смотрению (в главе 3) его следствий применительно к возмож­ности создания разумного робота-математика с компьютерным разумом, необходимо очень тщательно исследовать некоторое количество формальных моментов, связанных с получением вы­вода ^'. Если подобные возможные формальные «лазейки» вас не смущают и вы готовы принять на веру утверждение У (согласно которому, напомним, математики при установлении математиче­ской истины не применяют заведомо обоснованные алгоритмы), то вы, вероятно, предпочтете пропустить (или хотя бы на неко­торое время отложить) нижеследующие рассуждения и перейти непосредственно к главе 3. Более того, если вы готовы принять на веру и несколько более серьезный вывод, в соответствии с кото­рым принципиально невозможно алгоритмически объяснить ни математическое, ни какое-либо иное понимание, то вам, возмож­но, стоит перейти сразу ко второй части книги — задержавшись разве что на воображаемом диалоге в §3.23 (обобщающем наи­более важные аргументы главы 3) и выводах в § 3.28.

Существует несколько математических моментов, связан­ных с приведенным в §2.5 гёделевским доказательством, кото­рые не дают людям покоя. Попытаемся с этими моментами разо­браться.

Q1. Я  понимаю так,  что  процедура А является единичной, тогда как во всевозможных математи­ческих обоснованиях мы, несомненно, применяем много разных способов рассуждения. Не следует ли нам принять во внимание возможность существования целого ряда возможных «процедур А»?

В действительности, использование мною такой формули­ровки вовсе не влечет за собой потери общего характера рас­суждений в целом. Любой конечный ряд ai, Ау, аз, ..., Аг ал­горитмических процедур всегда можно выразить в виде единич­ного алгоритма А, причем таким образом, что А окажется неза­вершаемым только в том случае, если не завершаются все от­дельные алгоритмы ai, ..., Ат. (Процедура А может протекать, например, следующим образом: «Выполнить первые 10 шагов алгоритма А\, запомнить результат; выполнить первые 10 шагов алгоритма А^\ запомнить результат; выполнить первые 10 шагов алгоритма аз', запомнить результат; и так далее вплоть до Аг затем вернуться к А\ и выполнить следующие 10 шагов; запо­мнить результат и т. д.; затем перейти к третьей группе из 10 ша­гов и т. п. Завершить процедуру, как только завершится любой из алгоритмов Д.».) Если же ряд алгоритмов А бесконечен, то для того, чтобы его можно было считать алгоритмической про­цедурой, необходимо найти способ порождения всей совокупно­сти алгоритмов ai, А-2, А3, ... алгоритмическим путем. Тогда мы сможем получить единичный алгоритм А, который заменяет весь ряд алгоритмов и выглядит приблизительно следующим образом:

«первые 10 этапов-A1;

вторые 10 этаповА1, первые 10 этаповА2;

третьи 10 этапов A1, вторые 10 этаповА2, первые 10 этаповА3;

… и т.д.»…

Завершается такой алгоритм лишь после успешного завершения любого алгоритма из ряда, и никак не раньше.

С другой стороны, можно представить себе ситуацию, когда ряд a1, a2, аз,…, предположительно бесконечный, заранее не задан даже в принципе. Время от времени к такому ряду добавля­ется следующая алгоритмическая процедура, однако изначально весь ряд в целом не определен. В этом случае, ввиду отсутствия какой-либо предварительно заданной алгоритмической процеду­ры для порождения такого ряда, единичный замкнутый алгоритм нам получить никак не удастся.

Q2. Мы, безусловно, должны допустить, что алгоритм А может оказаться и не фиксированным. Лю­ди, в конце концов, обладают способностью к обучению, а значит, применяемый ими при этом алгоритм вполне может претерпевать непрерывные из­менения.

Для описания изменяющегося алгоритма необходимо каким-то образом задать правила, согласно которым он, собственно, изменяется. Если сами по себе эти правила являются полностью алгоритмическими, то мы уже включили их в описание нашей гипотетической процедуры «А», иначе говоря, такой «изменя­ющийся алгоритм» на деле представляет собой всего-навсего еще один пример единичного алгоритма, и на наши рассужде­ния подобное допущение никак не влияет. С другой стороны, можно вообразить средства для изменения алгоритма, предпо­ложительно не являющиеся алгоритмическими: такие, например, как введение в алгоритм каких-то случайных составляющих или неких процедур взаимодействия его с окружением. «Неалгорит­мический» статус подобных средств изменения алгоритма мы еще будем рассматривать несколько позднее (см. §§ 3.9, 3.10); можно также вернуться к § 1.9, где было показано, что ни одно из этих средств не позволяет сколько-нибудь убедительно избавиться от алгоритмизма (как того требует точка зрения ^). В данном слу­чае, т. е. в рамках чисто математических рассуждений, нас зани­мает лишь возможность того, что такое изменение действительно будет носить алгоритмический характер. Если же предположить, что алгоритмическим оно быть никак не может, то мы, без­условно, придем к полному согласию с выводом &.

Пожалуй, следует немного подробнее остановиться на том, что может обозначать определение «алгоритмически изменяю­щийся» применительно к алгоритму А. Допустим, что алгоритм А зависит не только от q и п, но и еще от одного параметра t, который можно рассматривать как «время», а можно как просто количество предшествующих настоящему моменту случаев ак­тивации нашего алгоритма. Как бы то ни было, мы можем так­же предположить, что параметр t является натуральным числом, и записать следующий ряд алгоритмов At (<J, n):

A0(q,n), Ai(q,n), A2(q,n), A3(q, n), ..., каждый элемент которого предположительно является обосно­ванной процедурой для установления незавершаемости вычисле­ния Cq (n), при этом мы будем считать, что мощность этих проце­дур возрастает по мере увеличения t. Предполагается также, что способ, посредством которого увеличивается мощность этих про­цедур, является алгоритмическим. Возможно, этот «алгоритми­ческий способ» зависит некоторым образом от «опыта» выпол­нения предыдущих алгоритмов At (q, n), однако в данном случае мы предполагаем, что этот «опыт» порождается также алгорит­мически (в противном случае мы снова приходим к согласию с ), т.е. мы имеем полное право включить «опыт» (или способы его порождения) в перечень операций, составляющих следующий ал­горитм (т.е., собственно, в At (q. n)). Действуя таким образом, мы опять-таки получаем единичный алгоритм (At (q, n)), кото­рый зависит алгоритмически от всех трех параметров: t, q, п. На его основе можно построить алгоритм Л*, столь же мощный, что и весь ряд At (q, п), однако зависящий только от двух натуральных чисел: q и п. Для получения такого A* (q, n) нам, как и преж­де, необходимо лишь выполнить первые десять шагов алгорит­ма ао (q, n) и запомнить результат; затем первые десять шагов алгоритма А1 (q, n) и вторые десять шагов алгоритма ао (q, n), запоминая получаемые результаты; затем первые десять шагов алгоритма A2 (q, n), вторые десять шагов алгоритма А1(q, n), третьи десять шагов алгоритма A0 (q, n) и т. д., "запоминая по­лучаемые на каждом шаге вычисления результаты. В конечном итоге, сразу после завершения любого из составляющих алго­ритм вычислений завершается выполнение и всей процедуры в целом. Замена процедуры А процедурой А* никак не влияет на ход рассуждений, посредством которых мы пришли к выводу .

Q3. Не был ли я излишне категоричен, утверждая, что в тех случаях, когда уже можно определенно утверждать, что данное вычисление Сq(п) и вправду завершается, алгоритм А все равно должен вы­полняться бесконечно? Допусти мы, что А в таких случаях также завершается, все наше рассужде­ние оказалось бы ложным. В конце концов, обще­известно, что присущая людям способность к ин­туитивному пониманию позволяет им порой делать заключение о возможности завершения того или иного вычисления, однако я, судя по всему, здесь этой способностью пренебрег. Не слишком ли мно­го искусственных ограничений?

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

Если вас такое положение дел не устраивает, попробуйте представить алгоритм А следующим образом: пусть А объединя­ет в себе оба вида понимания, но в том случае, когда выясняется, что вычисление Cq(n) действительно завершается, алгоритм А искусственно зацикливается (т. е. выполняет какую-то операцию снова и снова, бесконечное количество раз). Разумеется, на са­мом деле математики работают иначе, однако дело не в этом. Наше рассуждение построено как redactio ad absurdum, т.е. начав с допущения, что для установления математической исти­ны используются заведомо обоснованные алгоритмы, мы в итоге приходим к противоположному выводу. Такое доказательство не требует, чтобы гипотетическим алгоритмом непременно оказался какой-то конкретный алгоритм А, мы вполне можем заменить его на другой алгоритм, построенный на основе А, — как, например, в только что упомянутом случае.

Этот комментарий применим и к любому другому возраже­нию вида: «А что если алгоритм А завершится по какой-либо совершенно посторонней причине и не даст нам доказательства того, что вычисление Cq (n) не завершается?». Если нам вдруг придется иметь дело с алгоритмом «Л», который ведет себя по­добным образом, то мы просто применим представленное в §2.5 обоснование к немного другому А — а именно, к такому, который зацикливается всякий раз, когда исходный «Л» завершается по любой из упомянутых посторонних причин.

Q4. Судя по всему, каждое вычисление Cq в пред­ложенной мною последовательности С0, С1, С2,… является вполне определенным, тогда как при лю­бом прямом переборе (численном или алфавит­ном) компьютерных программ ситуация, конечно же, была бы иной?

В самом деле, было бы весьма затруднительно однознач­но гарантировать, что каждому натуральному числу q в нашей последовательности действительно соответствует некое рабочее вычисление Cq. Например, описанная в НРК последователь­ность машин Тьюринга Тд этому условию, конечно же, не удовле­творяет; см. НРК, с. 54. При определенных значениях q маши­ну Тьюринга Tq можно назвать «фиктивной» по одной из четырех причин: ее работа никогда не завершается; она оказывается «некорректно определенной», поскольку представление числа n в виде двоичной последовательности содержит слишком много (пять или более) единиц подряд и, как следствие, не имеет интер­претации в данной схеме; она получает команду, которая вводит ее в нигде не описанное внутреннее состояние; или же по за­вершении работы она оставляет ленту пустой, т. е. не дает ника­кого численно интерпретируемого результата. (См. также При­ложение А.) Для приведенного в §2.5 доказательства Гёделя-Тьюринга вполне достаточно объединить все эти причины в одну категорию под названием «вычисление не завершается». В част­ности, когда я говорю, что вычислительная процедура А «завер­шается» (см. также примечание на с. 122), я подразумеваю, что она «завершается» как раз в вышеупомянутом смысле (а пото­му не содержит неинтерпретируемых последовательностей и не оставляет ленту пустой), — иными словами, «завершиться» мо­жет только действительно корректно определенное рабочее вы­числение. Аналогично, фраза «вычисление Cq (n) завершается» означает, что данное вычисление корректно завершается именно в этом смысле. При такой интерпретации соображение Q4 не имеет совершенно никакого отношения к представленному мною доказательству.

Q5. Не является ли мое рассуждение лишь демонстрацией неприменимости некоей частной алго­ритмической процедуры (А) к выполнению вычис­ления Cq (n)? И каким образом оно показывает, что я справлюсь с задачей лучше, чем какая бы то ни было процедура A?

Оно и в самом деле вполне однозначно показывает, что мы справляемся с такого рода задачами гораздо лучше любого ал­горитма. Поэтому, собственно, я и воспользовался в своем рас­суждении приемом reductio ad absurdum. Пожалуй, в данном случае уместно будет привести аналогию. Читателям, вероятно, известно о евклидовом доказательстве невозможности отыскать наибольшее простое число, также основанном на reductio ad absurdum. Доказательство Евклида выглядит следующим обра­зом. Допустим, напротив, что такое наибольшее простое число нам известно; назовем его р. Теперь рассмотрим число N, кото­рое представляет собой сумму произведения всех простых чисел вплоть до р и единицы:

N = 2*3*5* ... * р + 1.

Число N, безусловно, больше р, однако оно не делится ни на одно из простых чисел 2, 3, 5, ..., р (поскольку при делении получаем единицу в остатке), откуда следует, что N либо и есть искомое наибольшее простое число, либо оно является составным, и тогда его можно разделить на простое число, большее р. И в том, и в другом случае мы находим простое число, большее р, что проти­воречит исходному допущению, заключавшемуся в том, что р есть наибольшее простое число. Следовательно, наибольшее простое число отыскать нельзя.

Такое рассуждение, основываясь на reductio ad absurdum, не просто показывает, что требуемому условию не соответству­ет некое частное простое число р, поскольку можно отыскать число больше него; оно показывает, что наибольшего простого числа просто не может существовать в природе. Аналогично, представленное выше доказательство Гёделя—Тьюринга не про­сто показывает, что нам не подходит тот или иной частный алго­ритм А, оно демонстрирует, что в природе не существует алго­ритма (познаваемо обоснованного), который был бы эквивален­тен способности человека к интуитивному пониманию, которую мы применяем для установления факта незавершаемости тех или иных вычислений.

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

Отыскание конкретного вычисления Ck (k) при заданном алгоритме А, безусловно, представляет собой вычислительный процесс. Более того, это можно достаточно явно показать. Означает ли это, что предположительно неалгоритмическая математи­ческая интуиция — интуиция, благодаря которой мы определяем, что вычисление Ck (k) никогда не завершается — на деле явля­ется все же алгоритмической?

Думаю, данное суждение следует рассмотреть более подроб­но, поскольку оно представляет собой одно из наиболее рас­пространенных недоразумений, связанных с гёделевским доказа­тельством. Следует особо уяснить, что оно не сводит на нет ничего из сказанного ранее. Хотя процедуру отыскания вычис­ления Ck (k) с помощью алгоритма А можно представить в виде вычисления, это вычисление не входит в перечень процедур, со­держащихся в Л. И не может входить, поскольку самостоятель­но алгоритм А не способен установить истинность Ck (k), тогда как новое вычисление (вкупе с А], судя по всему, вполне на это способно. Таким образом, несмотря на то, что с помощью нового вычисления действительно можно отыскать вычисление Ck (k), членом клуба «официальных установителей истины» оно не яв­ляется.

Изложим все это несколько иначе. Вообразите себе управ­ляемого компьютером робота, способного устанавливать мате­матические истины с помощью алгоритмических процедур, со­держащихся в А. Для большей наглядности я буду пользоваться антропоморфной терминологией и говорить, что робот «знает» те математические истины (в данном случае — связанные с установ­лением факта незавершаемости вычислений), которые он может вывести, применяя алгоритм А. Однако если наш робот «знает» лишь А, то он никак не сможет «узнать», что вычисление Ck (k) не завершается, даже если процедура отыскания Ck (k) с по­мощью А является целиком и полностью алгоритмической. Мы, разумеется, могли бы сообщить роботу о том, что вычисле­ние Ck (k} и в самом деле не завершается (воспользовавшись для установления этого факта собственными пониманием и ин­туицией), однако, если робот примет это утверждение на «веру», ему придется изменить свои собственные правила, присоединив полученную новую истину к тем, что он уже «знает». Мы можем пойти еще дальше и каким-либо способом сообщить нашему ро­боту о том, что для получения новых истин на основании старых ему, помимо прочего, необходимо «знать» и общую вычислитель­ную процедуру отыскания Ck (k) посредством алгоритма А. К запасу «знаний» робота можно добавить все, что является вполне определенным и вычислительным по своей природе. Однако в ре­зультате у нас появляется новый алгоритм «Л», и доказательство Гёделя следует применять уже к нему, а не к старому А. Иначе говоря, везде вместо старого А нам следовало бы использовать новый «Л», поскольку менять алгоритм «Л» посреди доказатель­ства есть не что иное, как жульничество. Таким образом, как мы видим, изъян возражения Q6 очень похож на рассмотренный выше изъян Q5. В нашем reductio ad absurdum мы полагаем, что алгоритм А (под которым понимается некая познаваемая и обоснованная процедура для установления факта незавершаемости вычислений) в действительности представляет собой всю совокупность известных математикам подобных процедур, из чего и следует противоречие. Попытку введения еще одной вы­числительной процедуры для установления истины — процеду­ры, не содержащейся в А, — после того как мы договорились, что А представляет собой всю их совокупность, я расцениваю как жульничество.

Беда нашего злосчастного робота в том, что, не обладая ка­ким бы то ни было пониманием гёделевской процедуры, он не располагает ни одним надежным и независимым способом уста­новления истины — истину ему сообщаем мы. (Эта проблема, вообще говоря, не имеет никакого отношения к вычислитель­ным аспектам доказательства Гёделя.) Для того чтобы достичь чего-то большего, ему, как и всем нам, необходимо понимание смысла операций, которые ему велено выполнять. Если тако­го понимания нет, то он вполне может «знать» (ошибочно), что вычисление Ck (k} завершается, а вовсе не наоборот. Заклю­чение (ошибочное) «вычисление Ck (&) завершается» выводится точно так же алгоритмически, как и заключение (правильное) «вычисление Ck (k) не завершается». Таким образом, дело во­все не в алгоритмическом характере этих операций, а в том, что для различения между алгоритмами, приводящими к истинным заключениям, и теми, что приводят к заключениям ложным, наш робот нуждается в способности выносить достоверные сужде­ния об истинности. Далее, на данной стадии рассуждения, мы все еще допускаем возможность того, что процесс «понимания» представляет собой некую разновидность алгоритмической дея­тельности, которая не содержится ни в одной из точно заданных и «заведомо» обоснованных процедур типа А. Например, пони­мание может осуществляться посредством выполнения какого-то необоснованного или непознаваемого алгоритма. В дальнейшем (см. главу 3) я попробую убедить читателя в том, что в действи­тельности понимание вообще не является алгоритмической дея­тельностью. На настоящий же момент нас интересуют всего лишь строгие следствия из доказательства Гёделя—Тьюринга, а на них возможность получения вычисления С^ (k) из процедуры А вы­числительным путем никоим образом не влияет.

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

Несмотря на кажущуюся логичность этого утверждения, здесь упущен из виду один очень существенный момент, а именно: способ, посредством которого мы (или компьютеры) определяем, какие математические утверждения истинны, а какие — ложны. (Во всяком случае, на простое хранение математических утвер­ждений способны и системы, гораздо менее сложные, нежели универсальный компьютер — например, фотоаппараты.) Прин­цип использования компьютера в Q7 совершенно не учитывает критического вопроса о наличии у этого самого компьютера спо­собности суждения об истинности. С равным успехом мож­но вообразить и компьютеры, в памяти которых не содержится ничего, кроме перечня абсолютно ложных математических «тео­рем», либо случайным образом перемешанных истинных и лож­ных утверждений. Откуда мы узнаем, какому компьютеру можно доверять? Я отнюдь не утверждаю, что эффективное моделиро­вание результатов сознательной интеллектуальной деятельности человека (в данном случае, в области математики) абсолютно невозможно, поскольку по одной лишь чистой случайности ком­пьютер может «умудриться» сделать все правильно, пусть и не обладая каким бы то ни было пониманием. Однако шансы на это до абсурдного малы, в то время как те вопросы, на которые мы здесь пытаемся найти ответ (например, каким таким образом мы определяем, что вот это математическое утверждение истинно, а вот это — ложно?), в возражении Q7 и вовсе не затрагиваются. С другой стороны, Q7 все же напоминает об одном более существенном соображении. Имеет ли непосредственное отно­шение к нашему исследованию обсуждение бесконечных струк­тур (всех натуральных чисел или всех вычислений), если учесть, что совокупность всех результатов, полученных на тот или иной момент времени всеми людьми и компьютерами, имеет конечную величину? В следующем комментарии мы рассмотрим этот без­условно важный вопрос отдельно.

Q8. Незавершающиеся вычисления суть идеализи­рованные математические конструкции, по опре­делению бесконечные. Вряд ли подобные вопросы могут иметь сколько-нибудь непосредственное от­ношение к изучению конечных физических объек­тов — таких, как компьютеры или мозг.

Все верно, рассуждая в идеализированном ключе о машинах Тьюринга, незавершающихся вычислениях и т. п., мы рассматри­вали бесконечные (потенциально) процессы, тогда как в случае людей или компьютеров нам приходится иметь дело с системами конечными. И, разумеется, применяя подобные идеализирован­ные доказательства к реальным и конечным физическим объек­там, следует быть готовыми к тому, что такая операция непре­менно окажется связанной с теми или иными ограничениями и оговорками. Однако, как выясняется, учет конечной природы ре­альных объектов не изменяет сколько-нибудь существенно сути доказательства Гёделя—Тьюринга. Нет ничего странного в том, что мы рассуждаем об идеализированных вычислениях, обосно­вываем те или иные умозаключения и выводим, математически, их теоретические ограничения. Можно, к примеру, обсуждать в аб­солютно конечных терминах вопрос о том, существует ли нечет­ное число, являющееся суммой двух четных чисел, или существу­ет ли натуральное число, не являющееся суммой четырех квад­ратов (как в приведенных выше задачах (С) и (В)), нисколько не смущаясь тем, что при рассмотрении этих вопросов мы неявно учитываем бесконечное множество всех натуральных чисел. Мы имеем полное право рассуждать о незавершающихся вычисле­ниях или машинах Тьюринга вообще, как о математических структурах, пусть и не в силах создать на практике бесконеч­но работающую машину Тьюринга. (Отметим, в частности, что действие машины Тьюринга, занятой поисками нечетного числа, являющегося суммой двух четных чисел, строго говоря, практи­чески реализовать невозможно, так как ее детали износятся го­раздо раньше, чем минет вечность.) Описание любого единичного вычисления (или действия машины Тьюринга) — задача вполне конечная, а вопрос о том, завершится ли в конечном итоге это вычисление, можно полагать вполне определенным. Сначала мы доводим до логического завершения теоретические рассуждения, связанные с теми или иными идеализированными вычислениями, и лишь затем пытаемся разглядеть, каким образом наши рассу­ждения применимы к конечным физическим системам — таким, как реально существующие компьютеры или люди.

Ограничения конечного характера могут быть обусловлены либо тем, что (i) описание конкретного рассматриваемого вы­числения оказывается слишком громоздким (т. е. число п в Сп или пара чисел q, n в Cq (n) оказываются слишком велики для того, чтобы их мог описать человек или реально существующий компьютер), либо тем, что (п) при внешней простоте описания вычисление, тем не менее, требует для своего выполнения чрез­мерно много времени, в результате чего может показаться, что оно не завершается вовсе, хотя теоретически данное вычисле­ние должно в конечном счете завершиться. На деле же, как мы вскоре убедимся, выясняется, что из этих двух условий сколько-нибудь существенное влияние на наши рассуждения оказыва­ет только (i), да и оно не так уж и велико. Незначительность фактора (ii), быть может, покажется вам удивительной. Суще­ствует множество относительно простых вычислений, которые в конечном счете завершаются, однако точки их завершения путем прямого вычисления не способен достичь ни один потенциально возможный компьютер. Рассмотрим, например, следующую задачу: «распечатать последовательность из 2^2^65536 единиц, после чего остановиться». (В §3.26 будут предложены еще несколько подобных примеров, гораздо более интересных с математической точки зрения.) Вопрос о завершаемости того или иного вычис­ления не следует решать путем прямого вычисления: этот метод зачастую оказывается крайне неэффективным.

Для того чтобы выяснить, каким образом ограничения (i) или (ii) могут повлиять на наши гёделевские рассуждения, пройдемся еще раз по соответствующим частям доказательства. В соответ­ствии с ограничением (i), вместо бесконечного ряда вычислений, мы располагаем рядом конечным:

, , , , ,…,

где предполагается, что число Q задает наиболее громоздкое вы­числение, какое способен выполнить наш компьютер или чело­век. В случае с человеком вышеприведенное утверждение можно счесть несколько туманным. Впрочем, в настоящий момент нас не особенно заботит точное определение числа Q. (Вопрос о туман­ности утверждений, касающихся человеческих способностей, бу­дет рассмотрен ниже, в комментарии к возражению Q13 в § 2.10.) Кроме того, можно предположить, что, попытавшись применить упомянутые вычисления к какому-то конкретному натуральному числу п, мы обнаружим, что значение п ограничено некоторой фиксированной величиной N, поскольку наш компьютер (или че­ловек) оказывается не способен работать с числами, превыша­ющими N. (Строго говоря, следует учесть и возможность того, что число N не является фиксированным, но зависит от того или иного конкретного вычисления Cq, т. е. N может зависеть от q. Однако этот факт не влияет на наши рассуждения сколько-нибудь существенным образом.)

Как и ранее, мы рассматриваем некий обоснованный ал­горитм A (q, n), завершение выполнения которого равносиль­но доказательству того, что вычисление Cq (n) не завершается. Несмотря на то, что, в соответствии с ограничением (i), рассмот­рению подлежат только значения q, не превышающие Q, и только те значения п, не превышающие N, мы, говоря об «обоснован­ности», в действительности имеем в виду, что алгоритм А должен быть обоснованным для всех значений q и п, независимо от их величины. (Таким образом, можно видеть, что правила, реализуе­мые в алгоритме А, являются точными математическими пра­вилами, в отличие от правил приближенных, работающих только в силу того или иного практического ограничения, налагаемого на «реально осуществимые» вычисления.) Более того, утверждая, что «вычисление Cq (n) не завершается», мы имеем в виду, что это вычисление действительно не завершается, а не то, что это вычисление просто-напросто оказывается слишком громоздким для того, чтобы его мог выполнить наш компьютер или человек,

как предусматривает ограничение (ii).

Вспомним, что утверждение (Н) гласит:

Если завершается вычисление А(а,п), то вычисление Cq (n) не завершается.

Принимая во внимание ограничение (ii), можно было бы предпо­ложить, что алгоритм А оказывается не слишком эффективен при установлении факта незавершаемости очередного вычисления, поскольку сам он состоит из большего количества шагов, чем способен выполнить компьютер или человек. Однако, как выяс­няется, для нашего доказательства этот факт не имеет никакого значения. Мы намерены отыскать некое вычисление A (k, k), ко­торое не завершается вообще. Для нас абсолютно неважно, что в некоторых других случаях, когда вычисление А действительно завершается, мы не можем об этом узнать, так как не в состоянии дождаться этого самого завершения.

Далее, как и в равенстве (J), мы вводим натуральное чис­ло k, при котором вычисление А (п, п) совпадает с вычислени­ем Ck (n) для всех n:

А(n,n) = Ck(n).

Следует, впрочем, рассмотреть еще предусматриваемую ограни­чением (i) возможность того, что упомянутое число k окажется больше Q. В случае какого-нибудь невообразимо сложного вы­числения А такая ситуация вполне возможна, однако только при условии, что это А уже начинает приближаться к верхней границе допустимой сложности (в смысле количества двоичных знаков в его описании в формате машины Тьюринга), с которой может работать наш компьютер или человек. Это обусловлено тем, что вычисление, получающее значение k из описания вычисления А (например, в формате машины Тьюринга), — вещь достаточно простая и может быть задана в явном виде (как уже было пока­зано в комментарии к Q6).

Вообще говоря, для того чтобы поставить в тупик алгоритм А, нам необходимо лишь вычисление Ck (k) — подставляя в (Н) равенство n = k, получаем утверждение (L):

Если завершается вычисление A(k, k), то вычисление Ck(k) не завершается.

Поскольку A (k, k) совпадает с Ck (k), наше доказательство по­казывает, что, хотя данное конкретное вычисление Ck (k) никогда не завершается, посредством алгоритма А мы этот факт устано­вить не в состоянии, даже если бы упомянутый алгоритм мог вы­полняться гораздо дольше любого предела, налагаемого на него в соответствии с ограничением (ii). Вычисление Ck (k) задается только введенным ранее числом k, и, при условии, что k не пре­вышает ни Q, ни N, это вычисление и в самом деле в состоянии выполнить наш компьютер или человек — в смысле, в состоянии начать. Довести его до завершения невозможно в любом случае, поскольку это вычисление просто-напросто не завершается!

А может ли число k оказаться больше Q или N? Такое воз­можно лишь в том случае, когда для описания А требуется так много знаков, что даже совсем небольшое увеличение их коли­чества выводит задачу за пределы возможностей нашего ком­пьютера или человека. При этом, поскольку мы знаем об об­основанности алгоритма А, мы знаем и о том, что рассматри­ваемое вычисление Ck(k) не завершается, даже если реальное выполнение этого вычисления представляет для нас проблему. Соображение (i), однако, предполагает и возможность того, что вычисление А окажется столь колоссально сложным, что одно лишь его описание вплотную приблизится к доступному вообра­жению человека пределу сложности, а сравнительно малое уве­личение количества составляющих его знаков даст в результате вычисление, превосходящее всякое человеческое понимание. Что бы мы о подобной возможности ни думали, я все же считаю, что любой столь впечатляющий набор реализуемых в нашем гипо­тетическом алгоритме А вычислительных правил окажется, вне всякого сомнения, настолько сложным, что мы не в состоянии будем наверняка знать, является ли он обоснованным, даже если нам будут точно известны все эти правила по отдельности. Таким образом, наше прежнее заключение остается в силе: при установлении математических истин мы не применяем познава­емо обоснованные наборы алгоритмических правил.

Не помешает несколько более подробно остановиться на сравнительно незначительном увеличении сложности, сопрово­ждающем переход от А к Ck(k). Помимо прочего, это существен­но поможет нам в нашем дальнейшем исследовании (в §§3.19 и 3.20). В Приложении А (с. 191) предложено явное описание вычисления Ck(k) в виде предписаний для машины Тьюринга, рассмотренных в НРК (глава 2). Согласно этим предписаниям, под обозначением Тт понимается «m-я машина Тьюринга». Для большего удобства и упрощения рассуждений здесь мы также будем пользоваться этим обозначением вместо «Сm», в част­ности, для определения степени, сложности вычислительной процедуры или отдельного вычисления. В соответствии с выше­сказанным, определим степень сложности  машины Тьюрин­га Тт как количество знаков в двоичном представлении числа т (см. НРК, с. 39); при этом степень сложности некоторого вы­числения Тт (п) определяется как большее из двух чисел  и v, где v — количество двоичных знаков в представлении числа п. Рассмотрим далее приведенное в Приложении А явное предпи­сание для составления вычисления Ck(k) на основании алгорит­ма А, заданного в упомянутых спецификациях машины Тьюринга. Полагая степень сложности А равной а, находим, что степень сложности явного вычисления Ck (k) не превышает числа а + 210 log2 (а + 336) — а это число, в свою очередь, оказывается лишь очень ненамного больше собственно а, да и то только тогда, когда число а очень велико.

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

ВЗГЛЯНУТЬ.

Q9. Точка зрения, известная как интуиционизм, не позволяет сделать вывод о непременной завершаемости  вычисления на определенном этапе на том лишь основании, что бесконечное продолжение этого вычисления приводит к противоречию; бытуют в математике и иные точки зрения сходного характера — например, «конструктивизм» и «финнтизм». Не окажется ли гёделевское доказательство спорным, будучи рассмотрено с этих позиций?

В своем гёделевском доказательстве (в частности, в утвер­ждении (М)) я использовал аргумент следующего вида: «Допу­щение о ложности X приводит к противоречию; следовательно, утверждение X истинно». Под «X» в данном случае следует по­нимать утверждение: «Вычисление Ck (k) не завершается». Это рассуждение относится к типу reductio ad absurdum; что же касается доказательства Гёделя в целом, то оно и в самом деле построено именно таким образом. Направление же в математике, называемое «интуиционизмом» (у истоков которого стоял гол­ландский математик Л. Э. Я. Брауэр; см. [222] и НРК, с. 113— 116), отрицает возможность построения обоснованного доказа­тельства на основе reductio ad absurdum. Интуиционизм возник приблизительно в 1912 году как реакция на некоторые сформи­ровавшиеся к концу девятнадцатого — началу двадцатого века математические тенденции, суть которых сводится к следующему: математический объект можно полагать «существующим» даже в тех случаях, когда нет никакой возможности этот объект так или иначе воплотить в действительности. А надо сказать, что слиш­ком вольное применение крайне расплывчатой концепции мате­матического существования и впрямь приводит порой к весь­ма неприятным противоречиям. Самый известный пример такого противоречия связан с парадоксальным «множеством всех мно­жеств, не являющихся членами самих себя» Бертрана Рассела. (Если множество Рассела является членом самого себя, то оно таковым не является; если же оно членом самого себя не явля­ется, то оно им, как ни странно, является! Подробнее см. §3.4 и НРК, с. 101.) Дабы противостоять общей тенденции, в рам­ках которой могут считаться «существующими» весьма вольно определенные математические объекты, интуиционисты полага­ют необоснованным математическое рассуждение, позволяющее делать вывод о существовании того или иного математического объекта на основании одной лишь противоречивости его несуще­ствования. Доказательство существования объекта посредством reductio ad absurdum не дает абсолютно никаких оснований по­лагать, что упомянутый объект действительно можно построить. Каким  же  образом  запрет на  применение  reductio  ad absurdum может повлиять на наше гёделевское доказательство? Вообще говоря, совсем не может, по той простой причине, что reductio ad absurdum мы применяем, если можно так выра­зиться, наоборот, то есть противоречие в нашем случае выво­дится из допущения, что нечто существует, а не из обратного допущения. С интуиционистской точки зрения все выглядит со­вершенно законно: мы заключаем, что объект не существует, на том основании, что противоречие возникает как раз из допуще­ния о существовании этого самого объекта. Предложенное мною гёделевское доказательство, по сути своей, является в интуицио­нистском смысле абсолютно приемлемым. (См. [222], с. 492.)

Аналогичные рассуждения применимы и ко всем прочим «конструктивистским» или «финитистским» направлениям в ма­тематике, о каких мне известно. Комментарий к возражению Q8 демонстрирует, что даже та точка зрения, согласно которой по­следовательность натуральных чисел нельзя считать «на самом деле» бесконечной, не освобождает нас от неизбежного вывода: для установления математической истины мы таки не пользуемся познаваемо обоснованными алгоритмами.