Новый ум короля: О компьютерах, мышлении и законах физики - [64]

(n), которое попадает в поле его действия. Это все будут ложные утверждения S(n), так что наша процедура, по сути, обеспечит нам рекурсивную нумерацию множества таких утверждений. Но выше мы установили, что это множество не нумеруемо таким образом. Это противоречие показывает, что дополнение Р все-таки не может быть рекурсивно пронумеровано; а Р, следовательно, не является рекурсивным, что и требовалось доказать.

Эти свойства с очевидностью демонстрируют, что наша формальная система не может быть полной: то есть всегда будут существовать утверждения, чью справедливость (или ложность) невозможно доказать в рамках системы. Ведь если предположить, что такие «неразрешимые» утверждения не существуют, то дополнение множества Р с необходимостью было бы множеством опровергаемых утверждений (все, что недоказуемо, обязано быть опровергаемо). Но мы уже знаем, что опровергаемые утверждения составляют рекурсивно нумеруемое множество, что делает Ррекурсивным. Однако, Р не рекурсивно — противоречие, которое доказывает требуемую неполноту. Это основное утверждение теоремы Геделя.

А как насчет подмножества T множества N, которое состоит из истинных утверждений нашей формальной системы? Рекурсивно ли T? Или оно только рекурсивно нумеруемо? А его дополнение? Оказывается, что ответ на все эти вопросы — отрицательный. Один из способов установить это — воспользоваться сделанным ранее выводом о невозможности алгоритмически сгенерировать ложные утверждения вида «Т_n(n) останавливается». Как следствие, ложные утверждения в целом не могут быть получены с помощью алгоритма, поскольку такой алгоритм, в частности, пронумеровал бы все вышеупомянутые ложные «Т_n(n) останавливается»-утверждения. Аналогично, и множество всех истинных утверждений не может быть построено при помощи алгоритма (так как любой подобный алгоритм легко модифицируется для нахождения ложных утверждений путем отрицания каждого из генерируемых им утверждений).

Поскольку, тем самым, истинные утверждения не являются (равно как и ложные) рекурсивно нумеруемыми, то они образуют гораздо более глубокий и сложноорганизованный массив, чем утверждения, имеющие доказательство внутри системы. И это иллюстрирует еще один аспект теоремы Геделя: что понятие математической истины только частично досягаемо в рамках любой формальной системы.

Существуют некоторые простые классы истинных арифметических утверждений, которые все же образуют рекурсивно нумеруемые множества. Например, как это нетрудно видеть, истинные утверждения вида

E_к.с.ω, x…, z[f (ω, x,…,z) = 0],

где f () — некоторая функция, построенная из обычных арифметических операций сложения, вычитания, умножения и возведения в степень, составляют рекурсивно нумеруемые множества[83] (которые я обозначу через А). Пример утверждения такого рода — хотя мы не знаем, верно ли оно — это отрицание последней теоремы Ферма[84]., для которой мы можем взять за f () функцию

f (ω, х, у, z) = (х+1)^ω+3 + (у+1)^ω+3- (z+1)^ω+3.

Однако, множество А не является рекурсивным (факт, который не так легко установить, хотя он и вытекает из оригинального доказательства Геделя). Значит, мы не имеем никаких алгоритмических средств для выяснения — хотя бы в принципе — истинности или ложности последней теоремы Ферма.

Рис. 4.1. Очень схематичное представление рекурсивного множества

На рис. 4.1 я попытался схематически представить рекурсивное множество как фигуру с простой и изящной границей, так что кажется, что определить непосредственно принадлежность произвольной точки этому множеству — дело несложное. Каждая точка на рисунке соответствует некоторому натуральному числу. При этом дополнительное множество также представлено в виде просто выглядящей области на плоскости. На рис. 4.2 я постарался изобразить рекурсивно нумеруемое, но не рекурсивное множество в виде области со сложной границей, где подразумевается, что множество с одной стороны границы, — той, что рекурсивно нумеруема — должно выглядеть проще, чем с другой.

Рис. 4.2. Очень схематичное представление рекурсивно нумеруемого множества (темная область), которое не является рекурсивным. Здесь светлая область определяется только по «остаточному принципу», когда удаляется темная часть, построенная при помощи вычислений; а установить путем прямых вычислений, принадлежит ли заданная точка белой области, нельзя

Фигуры очень схематичны и не претендуют на какую бы то ни было «геометрическую аккуратность». И конечно же, не стоит придавать большого значения тому, что эти рисунки изображены так, как если бы они были расположены на двумерной плоскости!

На рис. 4.3 я схематично обозначил, как расположены области Р, Т и А внутри множества N.

Рис. 4.3. Очень схематичное представление различных множеств утверждений. Множество Р утверждений, доказуемых в рамках системы, является, как и А, рекурсивно нумеруемым, но не рекурсивным. Множество Т истинных утверждений даже не рекурсивно нумеруемо

Является ли множество Мандельброта рекурсивным?

Существенной характеристикой нерекурсивных множеств является их сложноорганизованность. Это свойство должно, в некотором смысле, препятствовать любым попыткам систематизации, которая, в противном случае, привела бы к некоторой «работающей» алгоритмической процедуре. Для нерекурсивного множества не существует общего алгоритмического пути к решению вопроса о принадлежности ему произвольного элемента (или «точки»), В начале третьей главы мы встретились с неким чрезвычайно сложно выглядящим множеством — с множеством Мандельброта. Хотя правила, по которым оно строится, поразительно просты, само множество представляет собой бесконечное разнообразие в высшей степени замысловатых структур. Может ли это быть примером настоящего нерекурсивного множества, явленного глазам смертных?