речь идет о доказательстве истинности равенства a × b = b × a, приведенном в §1.19. Тоже вполне достойное «доказательство», хотя формальным его назвать нельзя.

Представленное выше рассуждение о суммировании последовательных шестиугольных чисел можно при желании заменить более формальным математическим доказательством. В основу такого формального доказательства можно положить принцип математической индукции, т.е. процедуру установления истинности утверждения в отношении всех натуральных чисел на основании одного-единственного вычисления. По существу, этот принцип позволяет заключить, что некое положение P(n), зависящее от конкретного натурального числа n (например, такое: «сумма первых n шестиугольных чисел равна n³»), справедливо для всех n, если мы можем показать, во-первых, что оно справедливо для n = 0 (или, в нашем случае, для n = 1), и, во-вторых, что из истинности P (n) следует истинность и P (n+1). Думаю, нет необходимости описывать здесь в деталях, как можно с помощью математической индукции доказать невозможность завершить вычисление (E); тем же, кого данная тема заинтересовала, рекомендую попытаться в качестве упражнения выполнить такое доказательство самостоятельно.

Всегда ли для установления факта действительной незавершаемости вычисления достаточно применить некие четко определенные правила — такие, например, как принцип математической индукции? Как ни странно, нет. Это утверждение, как мы вскоре увидим, является одним из следствий теоремы Гёделя, и для нас крайне важно попытаться его правильно понять. Причем недостаточной оказывается не только математическая индукция. Недостаточным будет какой угодно набор правил, если под «набором правил» подразумевать некую систему формализованных процедур, в рамках которой возможно исключительно вычислительным путем проверить корректность применения этих правил в каждом конкретном случае. Такой вывод может показаться чересчур пессимистичным, ибо он, по-видимому, означает, что, несмотря на то, что вычисления, которые нельзя завершить, существуют, сам факт их незавершаемости строго математически установить невозможно. Однако смысл упомянутого следствия из теоремы Гёделя заключается вовсе не в этом. На самом деле, все не так уж и плохо: способность понимать и делать выводы, присущая математикам — как, впрочем, и всем остальным людям, наделенным логическим мышлением и воображением, — просто-напросто не поддается формализации в виде того или иного набора правил. Иногда правила могут стать частичной заменой пониманию, однако в полной мере такая замена не представляется возможной.

Для того, чтобы понять, каким образом из теоремы Гёделя (в моей упрощенной формулировке, навеянной отчасти идеями Тьюринга) следует все вышесказанное, нам необходимо будет сделать небольшое обобщение для типов утверждений, относящихся к рассмотренным в предыдущем разделе вычислениям. Вместо того чтобы решать проблему завершаемости для каждого отдельного вычисления ((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 = 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, которая и в самом деле всегда дает верный ответ, мы будем называть