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

Пенроуз Роджер

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

останавливается»-утверждения. Аналогично, и множество всех истинныхутверждений не может быть построено при помощи алгоритма (так как любой подобный алгоритм легко модифицируется для нахождения ложных утверждений путем отрицания каждого из генерируемых им утверждений).

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

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

E _к.с. , x …, z [ f ( , x ,…, z ) = 0 ],

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

83

Мы нумеруем множества { v , , x …., z ], где v представляет функцию f в согласии с некоторой лексикографической схемой. Мы (рекурсивно) проверяем на каждом этапе справедливость равенства f ( , x …, z ) = 0 и оставляем утверждение E _к.с. , х …., z [( , х …., z ) = 0 ] только в том случае, если это равенство выполняется.

84

Последняя теорема Ферма доказана английским математиком Эндрю Уайлсом (Andrew J. Wiles). Доказательство опубликовано в 1995 году. — Прим. ред.

f ( , х , у , z ) = ( х + 1 ) ^{+ 3} + ( у + 1 ) ^{+ 3} – ( z + 1 ) ^{+ 3} .

Однако,

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

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

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

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

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

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

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

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

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

Читателю, однако, не понадобится много времени, чтобы сообразить, что эта парадигма сложности была создана специально для наших глаз волшебством вычислительных технологий с использованием современных быстродействующих компьютеров. А не являются ли компьютеры истинным воплощением алгоритмических действий? Конечно, это так, но все же мы должны принимать во внимание способ, с помощью которого компьютеры, в действительности, создают эти картинки. Чтобы проверить, принадлежит точка плоскости Аргана — комплексное число с — множеству Мандельброта (закрашено черным) или его дополнению (светлая область), компьютер, начиная с нуля, применит отображение