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

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

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.Очень схематичное представление различных множеств утверждений. Множество Р утверждений, доказуемых в рамках системы, является, как и А , рекурсивно нумеруемым, но не рекурсивным. Множество Т истинных утверждений даже не рекурсивно нумеруемо

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

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

z → z 2 + с

сначала к z = 0 , чтобы получить с ; потом к z = с , чтобы получить с 2 + с ; затем к z = с 2 + с , чтобы получить с 4 + 2с 3 + с 2 + с ; и так далее. Если эта последовательность 0 , с , с 2 + с , с 4 + 2с 3 + с 2 + с … остается ограниченной, то соответствующая точка с будет черной; в противном случае — белой. Как машина определяет, что такая последовательность остается ограниченной? В принципе, этот вопрос предполагает наличие информации о том, что происходит после бесконечного числа ее элементов! Сама по себе эта задача вычислительными методами не решается. К счастью, существуют способы предсказать исходя уже из конечного числа членов, когда последовательность станет неограниченной. (На самом деле, если последовательность достигает окружности радиуса 1 + √2 с центром в начале координат, можно с уверенностью сказать, что она будет неограниченной.)

Таким образом, дополнение к множеству Мандельброта является, в некотором смысле, рекурсивно нумеруемым. Если комплексное число с расположено в светлой области, то существует алгоритм, подтверждающий этот факт. А как насчет самого множества Мандельброта — темного участка рисунка? Существует ли алгоритм, способный точно установить, что точка, принадлежащая предположительно темному участку, действительно ему принадлежит? Ответ на этот вопрос в настоящее время, похоже, отсутствует [85]. Я справлялся у многих коллег и экспертов, но ни один из них не слышал о подобном алгоритме. Равно как и никто из них не сталкивался с указанием на то, что такого алгоритма не существует. По крайней мере, насколько можно об этом судить, алгоритм для темной области на сегодняшний день неизвестен. Возможно, множество, дополнительное по отношению к множеству Мандельброта, действительно является примером рекурсивно нумеруемого, но не рекурсивного множества!