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

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

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

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

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

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

Из этого следует заключить, что вычисление 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. Вывод:

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