Файл: Пеноуз Роджер. Тени разума. В поисках науки о сознании.doc

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

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

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

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