Тени разума. В поисках науки о сознании

Можно полагать, что процедура 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. Вывод: