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

E к.с. x [ K ( х )] является истинным. (Если бы такого числа не было, то наша операция повторялась бы «бесконечно» [81]), стараясь обнаружить несуществующее x .) В любом случае, предшествующие рассуждения показывают, что, исходя из результатов Тьюринга, программа Гильберта по сведению целых разделов математики к вычислениям в рамках некоторой формальной системы — невыполнима.

Как оказывается, эта процедура не может с очевидностью установить, что мы имеем утверждение Геделя (наподобие P k ( k ), которое верно , но внутри системы недоказуемо. Однако, если вспомнить доказательство, приведенное в главе 2 и показывающее, «как „перехитрить“ алгоритм» (см. подглаву «Как превзойти алгоритм»), то мы увидим, что можно сделать нечто похожее и в этом случае. В том доказательстве мы смогли выяснить, что для любого алгоритма, определяющего момент остановки машины Тьюринга, можно придумать такое действие машины, которое не прекращается, хотя алгоритм — в отличие от нас — «увидеть» это не способен. (Вспомните, что мы требовали от алгоритма корректно информировать нас о моменте, когда машина Тьюринга действительно остановится, хотя мы допускаем, что он может не оповестить нас, если машина на самом деле не прекратит свое действие, продолжая работать вечно.) Таким образом, как и в ситуации с теоремой Геделя, у нас есть утверждение (безостановочное действие машины Тьюринга), истинность которого мы можем установить при помощи интуитивного понимания, хотя определенная алгоритмическая процедура нам такой возможности и не дает.

Существует способ для описания основных результатов, полученных Геделем и Тьюрингом, в графическом виде, на языке теории множеств. Это позволит нам избежать произвольности описания в терминах конкретного символизма или в рамках формальной системы и выделить наиболее существенное. Мы будем рассматривать только множества натуральных чисел (конечные или бесконечные), такие как {4,5,8}, {0,57,100003}, {6}, {0}, {1,2,3,4….,9999}, {1,2, 3,4…. }, {0,2,4,6,8…. } ит. п.; или даже все множество N = {0,1,2,3,4… }, равно как и пустое множество ø = {}. Нас будут интересовать только вопросы вычислимости, скажем: «Какие множества натуральных чисел могут быть сгенерированы с помощью алгоритма, а какие — нет?»

Чтобы сформулировать такой вопрос, мы можем считать, что каждое отдельное число n обозначает определенную строчку символов некоторой формальной системы.

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

Давайте выберем формальную систему достаточно непротиворечивую и широкую для того, чтобы включать в себя все действия всех машин Тьюринга — и, более того, «имеющую смысл» с учетом требования «самоочевидной справедливости» ее аксиом и правил вывода. Далее, пусть ряд утверждений Q 0, Q 1 , Q 2 …. формальной системы имеет доказательства внутри системы. Эти «доказуемые» утверждения будут иметь номера, которые составляют некоторое множество в N — по сути, это множество Р «теорем», рассмотренных выше. Мы уже видели, что существует алгоритм для последовательного построения всех утверждений произвольно заданной формальной системы, имеющих доказательства. (Как отмечено ранее, « n - е доказательство» П n получается из n алгоритмически. Все, что нам надо — это посмотреть на последнюю строчку n - го доказательства, чтобы найти « n - е утверждение, доказуемое в рамках системы», т. е. n - ю «теорему».) Следовательно, мы имеем алгоритм последовательной генерации элементов Р (при которой возможны и повторения, что для нас не важно).

Множество типа Р , которое может быть построено с помощью некоторого алгоритма, называется рекурсивно нумеруемым . Заметьте, что множество утверждений, ложность которых может быть установлена в рамках системы — т. е. утверждений, чьи отрицания являются справедливыми — точно так же рекурсивно нумеруемо, поэтому мы можем просто нумеровать доказуемые утверждения по мере продвижения, учитывая и их отрицания. Есть большое число других, тоже рекурсивно нумеруемых, подмножеств N , для определения которых нам вовсе необязательно ссылаться на нашу формальную систему. Простыми примерами рекурсивно нумеруемых множеств могут служить множество четных чисел

{О, 2,4,6, 8…. }, множество квадратов

{0,1,4,9,16….} и множество простых чисел

{2,3,5, 7, И….}.

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

{1,3,5,7,9….}, {2,3,5,6,7,8,10….}

и

{0,1,4,6, 8,9,10,12….}.

Было бы достаточно просто указать алгоритм и для этих дополнительных множеств. Конечно же, мы можем выяснить алгоритмическим путем, является ли произвольное натуральное число n четным, квадратом натурального числа или простым числом, соответственно. Это дает нам алгоритм для построения обоих множеств, поскольку мы можем перебирать все натуральные числа и для каждого из них решать, принадлежит ли оно к определенному множеству или же к его дополнению. Множество, которое обладает свойством рекурсивной нумеруемости вместе со своим дополнением, называется рекурсивным . Очевидно, что дополнительное по отношению к рекурсивному множество также будет рекурсивным.