Семейства вычислений; следствие Гёделя — Тьюринга

Для того, чтобы понять, каким образом из теоремы Гёделя (в моей упрощенной формулировке, навеянной отчасти идеями Тьюринга) следует все вышесказанное, нам необходимо будет сделать небольшое обобщение для типов утверждений, относящихся к рассмотренным в предыдущем разделе вычислениям. Вместо того чтобы решать проблему завершаемое™ для каждого отдельного вычисления ((А), (В), (С), (D) или (Е)), нам следует рассмотреть некоторое общее вычисление, которое зависит от натурального числа n (либо как-то воздействует на него). Таким образом, обозначив такое вычисление через C(n), мы можем рассматривать его как целое семейство вычислений, где для каждого натурального числа (0, 1, 2, 3, 4,...) выполняется отдельное вычисление (соответственно, (C(0), С(1), С(2), С(3), С(4), ...), а сам принцип, в соответствии с которым вычисление зависит от n, является целиком и полностью вычислительным.

В терминах машин Тьюринга это всего лишь означает, что C(n) есть действие, производимое некоей машиной Тьюринга над числом п. Иными словами, число n наносится на ленту и подается на вход машины, после чего машина самостоятельно выполняет вычисления. Если вас почему-либо не устраивает концепция «машины Тьюринга», вообразите себе самый обыкновенный универсальный компьютер и считайте n «данными», необходимыми для работы какой-нибудь программы. Нас в данном случае интересует лишь одно: при любом ли значении nможет завершиться работа такого компьютера.

Для того чтобы пояснить, что именно понимается под вычислением, зависящим от натурального числа п, рассмотрим два примера.

(F)Найти число, не являющееся суммой квадратов n чисел,

(G)Найти нечетное число, являющееся суммой n четных чисел.

Припомнив, о чем говорилось выше, мы без особого труда убедимся, что вычисление (F) завершается только при n = 0, 1, 2 и 3 (давая в результате, соответственно, 1, 2, 3 и 7), тогда как вычисление (G) вообще не завершается ни при каком значении n. Вздумай мы действительно доказать, что вычисление (F) не завершается при n, равном или большем 4, нам понадобилась бы более или менее серьезная математическая подготовка (по крайней мере, знакомство с доказательством Лагранжа); с другой стороны, тот факт, что ни при каком n не завершается вычисление (G), вполне очевиден. Какими же процедурами располагают математики для установления незавершаемой природы таких вычислений в общем случае? Можно ли сами эти процедуры представить в вычислительной форме?

Предположим, что у нас имеется некая вычислительная процедура А, которая по своем завершении дает нам исчерпывающее доказательство того, что вычисление С(n) действительно никогда не заканчивается. Ниже мы попробуем вообразить, что А включает в себя все известные математикам процедуры, посредством которых можно убедительно доказать, что то или иное вычисление никогда не завершается. Соответственно, если в каком-то конкретном случае завершается процедура А, то мы получаем, в рамках доступного человеку знания, доказательство того, что рассматриваемое конкретное вычисление никогда не заканчивается. Большая часть последующих рассуждений не потребует участия процедуры А именно в такой роли, так как они посвящены, в основном, математическим умопостроениям. Однако для получения окончательного заключения У нам придется таки придать процедуре А соответствующий статус.

Я, разумеется, не требую, чтобы посредством процедуры А всегда можно было однозначно установить, что вычисление С(n) нельзя завершить (в случае, если это действительно так); однако я настаиваю на том, что неверных ответов А не дает, т. е. если мы с ее помощью пришли к выводу, что вычисление С(n) не завершается, значит, так оно и есть. Процедуру А, которая и в самом деле всегда дает верный ответ, мы будем называть обоснованной. Следует отметить, что если процедура А оказывается в действительности необоснованной, то этот факт, в принципе, можно установить с помощью прямого вычисления — иными словами, необоснованную процедуру А можно опровергнуть вычислительными методами. Так, если А ошибочно утверждает, что вычисление С(n) нельзя завершить, тогда как в действительности это не так, то выполнение самого вычисления С(n) в конечном счете приведет к опровержению А. (Возможность практического выполнения такого вычисления представляет собой отдельный вопрос, его мы рассмотрим в ответе на возражение Q8.)

Для того чтобы процедуру А можно было применять к вычислениям в общем случае, нам потребуется какой-нибудь способ маркировки различных вычислений С(n), допускаемый А. Все возможные вычисления С можно, вообще говоря, представить в виде простой последовательности

, , , , , ,…,

т. е. q-е вычисление при этом получит обозначение С_q. В случае применения такого вычисления к конкретному числу п будем записывать

С₀ (n), Ci (п), С₂ (п), С₃ (п), С₄ (п), С₅ (п), .... ,

Можно представить, что эта последовательность задается, скажем, как некий пронумерованный ряд компьютерных программ. (Для большей ясности мы могли бы, при желании, рассматривать такую последовательность как ряд пронумерованных машин Тьюринга, описанных в НРК; в этом случае вычисление C_q(n) представляет собой процедуру, выполняемую q-й машиной Тьюринга Т_q над числом n.) Здесь важно учитывать следующий технический момент: рассматриваемая последовательность является вычислимой — иными словами, существует одно-единственное вычисление С., которое, будучи выполнено над числом q, дает в результате С_q, или, если точнее, выполнение вычисления С, над парой чисел q, n (именно в таком порядке) дает в результате C_q (n).

Можно полагать, что процедура А представляет собой некое особое вычисление, выполняя которое над парой чисел q, n, можно однозначно установить, что вычисление C_q (n), в конечном итоге, никогда не завершится. Таким образом, когда завершается вычисление А, мы имеем достаточное доказательство того, что вычисление C_q (n) завершить невозможно. Хотя, как уже говорилось, мы и попытаемся вскоре представить себе такую процедуру А, которая формализует все известные современной математике процедуры, способные достоверно установить невозможность завершения вычисления, нет никакой необходимости придавать А такой смысл прямо сейчас. Пока же процедурой А мы будем называть любой обоснованный набор вычислительных правил, с помощью которого можно установить, что то или иное вычисление C_q (n) никогда не завершается. Поскольку выполняемое процедурой А вычисление зависит от двух чисел q и п, его можно обозначить как A (q, n) и записать следующее утверждение:

(Н) Если завершается A (q, n), то C_q (n) не завершается.

Рассмотрим частный случай утверждения (Н), положив q равным п. Такой шаг может показаться странным, однако он вполне допустим. (Он представляет собой первый этап мощного «диагонального доказательства» — процедуры, открытой в высшей степени оригинальным и влиятельным датско-русско-немецким математиком девятнадцатого века Георгом Кантором; эта процедура лежит в основе рассуждений и Гёделя, и Тьюринга.) При q, равном п, наше утверждение принимает следующий вид:

(I) Если завершается А (п, п), то С_п (п) не завершается.

Отметим, что А(n, n) зависит только от одного числа (n), а не от двух, так что данное вычисление должно принадлежать ряду , , , , …(по n), поскольку предполагается, что этот ряд содержит все вычисления, которые можно выполнить над одним натуральным числом n. Обозначив это вычисление через Ck, запишем:

(J) A(n,n) = C_k(n).

Рассмотрим теперь частный случай п = k. (Второй этап диагонального доказательства Кантора.) Из равенства (J) получаем:

(К)A(k,k) = C_k(k),

утверждение же (I) при n = k принимает вид:

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

Подставляя (К) в (L), находим:

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

Из этого следует заключить, что вычисление Ck (k) в действительности не завершается. (Ибо, согласно (М), если оно завершается, то оно не завершается!) Невозможно завершить и вычисление A (k, k), поскольку, согласно (К), оно совпадает с Ck (k). То есть, наша процедура А оказывается не в состоянии показать, что данное конкретное вычисление Ck (k) не завершается, даже если оно и в самом деле не завершается.

Более того, если нам известно, что процедура А обоснована, то, значит, нам известно и то, что вычисление Ck (k) не завершается. Иными словами, нам известно нечто, о чем посредством процедуры А мы узнать не могли. Следовательно, сама процедура А с нашим пониманием никак не связана.

В этом месте осторожный читатель, возможно, пожелает перечесть все вышеприведенное доказательство заново, дабы убедиться в том, что он не пропустил какой-нибудь «ловкости рук» с моей стороны. Надо признать, что, на первый взгляд, это доказательство и в самом деле смахивает на фокус, и все же оно полностью допустимо, а при более тщательном изучении лишь выигрывает в убедительности. Мы обнаружили некое вычисление Ck (k), которое, насколько нам известно, не завершается; однако установить этот факт с помощью имеющейся в нашем распоряжении вычислительной процедуры А мы не в состоянии. Это, собственно, и есть теорема Гёделя(—Тьюринга) в необходимом мне виде. Она применима к любой вычислительной процедуре А, предназначенной для установления невозможности завершить вычисление, — коль скоро нам известно, что упомянутая процедура обоснована. Можно заключить, что для однозначного установления факта незавершаемости вычисления не будет вполне достаточным ни один из заведомо обоснованных наборов вычислительных правил (такой, например, как процедура А), поскольку существуют незавершающиеся вычисления (например, Ck (k)), на которые эти правила не распространяются. Более того, поскольку на основании того, что нам известно о процедуре А и об ее обоснованности, мы действительно можем составить вычисление Ck (k}, которое, очевидно, никогда не завершается, мы вправе заключить, что процедуру А никоим образом нельзя считать формализацией процедур, которыми располагают математики для установления факта незавершаемости вычисления, вне зависимости от конкретной природы А. Вывод:

Для установления математической истины математики не применяют заведомо обоснованные алгоритмы.

Мне представляется, что к такому выводу неизбежно должен прийти всякий логически рассуждающий человек. Однако многие до сих пор предпринимают попытки этот вывод опровергнуть (выдвигая возражения, обобщенные мною под номерами Q1 — Q20 в §2.6 и §2.10), и, разумеется, найдется ничуть не меньше желающих оспорить вывод более строгий, суть которого сводится к тому, что мыслительная деятельность непременно оказывается связана с некими феноменами, носящими фундаментально невычислительный характер. Вы, возможно, уже спрашиваете себя, каким же это образом подобные математические рассуждения об абстрактной природе вычислений могут способствовать объяснению принципов функционирования человеческого мозга. Какое такое отношение имеет все вышесказанное к проблеме осмысленного осознания? Дело в том, что, благодаря этим математическим рассуждениям, мы и впрямь можем прояснить для себя некие весьма важные аспекты такого свойства мышления, как понимание — в терминах общей вычислимости, — а, как было показано в § 1.12, свойство понимания связано с осмысленным осознанием самым непосредственным образом. Предшествующее рассуждение действительно носит в основном математический характер, и связано это с необходимостью подчеркнуть одно очень существенное обстоятельство: алгоритм А участвует здесь на двух совершенно различных уровнях. С одной стороны, это просто некий алгоритм, обладающий определенными свойствами, с другой стороны, получается, что на самом-то деле А можно рассматривать как «алгоритм, которым пользуемся мы сами» в процессе установления факта незавершаемости того или иного вычисления. Так что в вышеприведенном рассуждении речь идет не только и не столько о вычислениях. Речь идет также и о том, каким образом мы используем нашу способность к осмысленному пониманию для составления заключения об истинности какого-либо математического утверждения — в данном случае утверждения о незавершаемости вычисления Ck (k). Именно взаимодействие между двумя различными уровнями рассмотрения алгоритма А — в качестве гипотетического способа функционирования сознания и собственно вычисления — позволяет нам сделать вывод, выражающий фундаментальное противоречие между такой сознательной деятельностью и простым вычислением.

Существуют, однако, всевозможные лазейки и контраргументы, на которые необходимо обратить самое пристальное внимание. Для начала, в оставшейся части этой главы, я тщательно разберу все важные контраргументы против вывода ^, которые когда-либо попадались мне на глаза — см. возражения Q1-Q20 и комментарии к ним в §§2.6 и 2.10; там, кроме того, можно найти и несколько дополнительных возражений моего собственного изобретения. Каждое из возражений будет разобрано со всей обстоятельностью, на какую я только способен. Пройдя через это испытание, вывод , как мы убедимся, существенно не пострадает. Далее, в главе 3, я рассмотрю следствия уже из утверждения . Мы обнаружим, что оно и в самом деле способно послужить прочным фундаментом для построения весьма убедительного доказательства абсолютной невозможности точного моделирования сознательного математического понимания посредством вычислительных процедур, будь то восходящих, нисходящих или любых их сочетаний. Многие сочтут такой вывод весьма неприятным, поскольку если он справедлив, то нам, получается, просто некуда двигаться дальше. Во второй части книги я выберу более позитивный курс. Я приведу правдоподобные, на мой взгляд, научные доводы в пользу справедливости результатов моих размышлений о физических процессах, которые могут, предположительно, лежать в основе деятельности мозга — вроде той, что осуществляется при нашем восприятии приведенных выше рассуждений, — и о причинах недоступности этой деятельности для какого бы то ни было вычислительного описания.

2.6. Возможные формальные возражения против

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

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

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

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

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

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

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

… и т.д.»…

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

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

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

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

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

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

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

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

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

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

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

В самом деле, было бы весьма затруднительно однозначно гарантировать, что каждому натуральному числу q в нашей последовательности действительно соответствует некое рабочее вычисление C_q. Например, описанная в НРК последовательность машин Тьюринга Т_д этому условию, конечно же, не удовлетворяет; см. НРК, с. 54. При определенных значениях q машину Тьюринга T_q можно назвать «фиктивной» по одной из четырех причин: ее работа никогда не завершается; она оказывается «некорректно определенной», поскольку представление числа n в виде двоичной последовательности содержит слишком много (пять или более) единиц подряд и, как следствие, не имеет интерпретации в данной схеме; она получает команду, которая вводит ее в нигде не описанное внутреннее состояние; или же по завершении работы она оставляет ленту пустой, т. е. не дает никакого численно интерпретируемого результата. (См. также Приложение А.) Для приведенного в §2.5 доказательства Гёделя-Тьюринга вполне достаточно объединить все эти причины в одну категорию под названием «вычисление не завершается». В частности, когда я говорю, что вычислительная процедура А «завершается» (см. также примечание на с. 122), я подразумеваю, что она «завершается» как раз в вышеупомянутом смысле (а потому не содержит неинтерпретируемых последовательностей и не оставляет ленту пустой), — иными словами, «завершиться» может только действительно корректно определенное рабочее вычисление. Аналогично, фраза «вычисление C_q (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 в C_q (n) оказываются слишком велики для того, чтобы их мог описать человек или реально существующий компьютер), либо тем, что (п) при внешней простоте описания вычисление, тем не менее, требует для своего выполнения чрезмерно много времени, в результате чего может показаться, что оно не завершается вовсе, хотя теоретически данное вычисление должно в конечном счете завершиться. На деле же, как мы вскоре убедимся, выясняется, что из этих двух условий сколько-нибудь существенное влияние на наши рассуждения оказывает только (i), да и оно не так уж и велико. Незначительность фактора (ii), быть может, покажется вам удивительной. Существует множество относительно простых вычислений, которые в конечном счете завершаются, однако точки их завершения путем прямого вычисления не способен достичь ни один потенциально возможный компьютер. Рассмотрим, например, следующую задачу: «распечатать последовательность из 2^2^65536 единиц, после чего остановиться». (В §3.26 будут предложены еще несколько подобных примеров, гораздо более интересных с математической точки зрения.) Вопрос о завершаемости того или иного вычисления не следует решать путем прямого вычисления: этот метод зачастую оказывается крайне неэффективным.

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

, , , , ,…,

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

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

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

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

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

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

А(n,n) = C_k(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? Такое возможно лишь в том случае, когда для описания А требуется так много знаков, что даже совсем небольшое увеличение их количества выводит задачу за пределы возможностей нашего компьютера или человека. При этом, поскольку мы знаем об обоснованности алгоритма А, мы знаем и о том, что рассматриваемое вычисление C_k(k) не завершается, даже если реальное выполнение этого вычисления представляет для нас проблему. Соображение (i), однако, предполагает и возможность того, что вычисление А окажется столь колоссально сложным, что одно лишь его описание вплотную приблизится к доступному воображению человека пределу сложности, а сравнительно малое увеличение количества составляющих его знаков даст в результате вычисление, превосходящее всякое человеческое понимание. Что бы мы о подобной возможности ни думали, я все же считаю, что любой столь впечатляющий набор реализуемых в нашем гипотетическом алгоритме А вычислительных правил окажется, вне всякого сомнения, настолько сложным, что мы не в состоянии будем наверняка знать, является ли он обоснованным, даже если нам будут точно известны все эти правила по отдельности. Таким образом, наше прежнее заключение остается в силе: при установлении математических истин мы не применяем познаваемо обоснованные наборы алгоритмических правил.

Не помешает несколько более подробно остановиться на сравнительно незначительном увеличении сложности, сопровождающем переход от А к C_k(k). Помимо прочего, это существенно поможет нам в нашем дальнейшем исследовании (в §§3.19 и 3.20). В Приложении А (с. 191) предложено явное описание вычисления Ck(k) в виде предписаний для машины Тьюринга, рассмотренных в НРК (глава 2). Согласно этим предписаниям, под обозначением Т_т понимается «m-я машина Тьюринга». Для большего удобства и упрощения рассуждений здесь мы также будем пользоваться этим обозначением вместо «С_m», в частности, для определения степени, сложности вычислительной процедуры или отдельного вычисления. В соответствии с вышесказанным, определим степень сложности машины Тьюринга Т_т как количество знаков в двоичном представлении числа т (см. НРК, с. 39); при этом степень сложности некоторого вычисления Т_т (п) определяется как большее из двух чисел и v, где v — количество двоичных знаков в представлении числа п. Рассмотрим далее приведенное в Приложении А явное предписание для составления вычисления Ck(k) на основании алгоритма А, заданного в упомянутых спецификациях машины Тьюринга. Полагая степень сложности А равной а, находим, что степень сложности явного вычисления Ck (k) не превышает числа а + 210 log₂ (а + 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демонстрирует, что даже та точка зрения, согласно которой последовательность натуральных чисел нельзя считать «на самом деле» бесконечной, не освобождает нас от неизбежного вывода: для установления математической истины мы таки не пользуемся познаваемо обоснованными алгоритмами.