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

Для того, чтобы понять, каким образом из теоремы Гёделя (в моей упрощенной формулировке, навеянной отчасти идеями Тьюринга) следует все вышесказанное, нам необходимо будет сделать небольшое обобщение для типов утверждений, относя­щихся к рассмотренным в предыдущем разделе вычислениям. Вместо того чтобы решать проблему завершаемое™ для каж­дого отдельного вычисления ((А), (В), (С), (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. Судя по всему, каждое вычисление C_q в пред­ложенной мною последовательности С0, С1, С2,… является вполне определенным, тогда как при лю­бом прямом переборе (численном или алфавит­ном) компьютерных программ ситуация, конечно же, была бы иной?

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

Q5. Не является ли мое рассуждение лишь демонстрацией неприменимости некоей частной алго­ритмической процедуры (А) к выполнению вычис­ленияC_q (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. Общая совокупность результатов, полученных всеми когда-либо жившими математиками, плюс совокупность результатов, которые будут получены всеми математиками за последующую, скажем, тысячу лет, — имеет конечную величину и может уместиться в банках памяти соответствующего ком­пьютера. Такой компьютер, естественно, способен

Наши рекомендации