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

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

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

В терминах машин Тьюринга это всего лишь означает, что C(n) есть действие, производимое некоей машиной Тьюринга над числом 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), вполне очевиден. Какими же процедурами располагают математики для установления незавершаемой природы таких вычислений в общем случае? Можно ли сами эти процедуры представить в вычислительной форме?

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

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

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

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

C₀, C₁, C₂, C₃, C₄, C₅, …,

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

C₀(n), C₁(n), C₂(n), C₃(n), C₄(n), C₅(n), ….

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

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

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

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

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

Отметим, что A(n, n) зависит только от одного числа (n), а не от двух, так что данное вычисление должно принадлежать ряду C₀, C₁, C₂, C₃, C₄, C₅, … (по n), поскольку предполагается, что этот ряд содержит все вычисления, которые можно выполнить над одним натуральным числом n. Обозначив это вычисление через C_k, запишем:

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

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

(K) A(k, k) = C_k(k),

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

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

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

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

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

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

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

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

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

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