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

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

Давайте выберем формальную систему достаточно непротиворечивую и широкую для того, чтобы включать в себя все действия всех машин Тьюринга — и, более того, «имеющую смысл» с учетом требования «самоочевидной справедливости» ее аксиом и правил вывода. Далее, пусть ряд утверждений Q ₀, Q ₁, Q ₂ …. формальной системы имеет доказательства внутри системы. Эти «доказуемые» утверждения будут иметь номера, которые составляют некоторое множество в 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 четным, квадратом натурального числа или простым числом, соответственно. Это дает нам алгоритм для построения обоих множеств, поскольку мы можем перебирать все натуральные числа и для каждого из них решать, принадлежит ли оно к определенному множеству или же к его дополнению. Множество, которое обладает свойством рекурсивной нумеруемости вместе со своим дополнением, называется рекурсивным. Очевидно, что дополнительное по отношению к рекурсивному множество также будет рекурсивным.

А существуют ли множества, которые рекурсивно нумеруемы, но рекурсивными, тем не менее, не являются? Давайте на минутку задумаемся над тем, какие следствия могут вытекать из подобного свойства. Поскольку элементы такого множества могут быть получены алгоритмическим путем, мы имели бы способ решить, принадлежит ли некоторый элемент — который, мы предполагаем, да, принадлежит множеству, — рассматриваемому множеству или нет. Все, что от нас требуется, — это запустить алгоритм и прогонять его через все элементы множества до тех пор, пока он не найдет элемент, который мы ищем. Теперь давайте предположим, что искомый элемент не принадлежит данному множеству. В таком случае использование нашего алгоритма ничего не даст: он будет работать вечно, будучи не в состоянии прийти к решению. В этом случае нам потребуется алгоритм для построения дополнительногопо отношению к исходному множества. Если этот алгоритм сможет обнаружить искомый элемент, то мы будем точно знать, что он не входит в состав исследуемого множества. Имея на вооружении оба алгоритма, мы так или иначе найдем данный элемент путем поочередного применения этих алгоритмов. Однако, такой благоприятный исход будет иметь место только в случае рекурсивногомножества. Мы же предполагаем, что мы рассматриваем множество рекурсивно нумеруемое, но при этом не рекурсивное, т. е. наш предполагаемый алгоритм для построения дополнительного множества просто не существует! Таким образом, мы имеем курьезную ситуацию, когда можно определить, включен ли элемент в множество при условии, что он ему наверняка принадлежит; но в то же время нельзя гарантировать, что мы сможем это сделать посредством какого бы то ни было алгоритма для элементов, которые множеству непринадлежат.

Может ли возникнуть такая ситуация в реальности? Есть ли и вправду рекурсивно нумеруемые множества, не являющиеся рекурсивными? А как насчет множества Р ? Имеет ли это множество свойство рекурсивности? Мы знаем, что оно рекурсивно нумеруемо, так что нам остается только выяснить, будет ли также дополнительное к нему множество обладать этим свойством.

Оказывается, что нет! Как мы можем сделать такой вывод? А давайте вспомним, что наряду с остальными операциями в нашей формальной системе разрешены и действия машин Тьюринга. Если мы обозначим n – юмашину Тьюринга через Т _n то выражение

« Т _n ( n ) останавливается»

— это утверждение — запишем его как S ( n ), — которое мы можем сформулировать в рамках нашей системы для любого n . Утверждение S ( n ) будет справедливым для одних значений n , и ложным — для остальных. Множество всех S ( n ), образованное перебором натуральных чисел 0,1, 2, 3…., будет представлено некоторым подмножеством N — скажем, S . Теперь учтем фундаментальный результат Тьюринга (глава 2, «Неразрешимость проблемы Гильберта»), который говорит о том, что не существует алгоритма, способного установить факт « Т _n ( n ) не останавливается» как раз в тех случаях, когда она действительно не останавливается. Это означает, что множество, состоящее из отрицаний S ( n ), не является рекурсивно нумеруемым.

Мы видим, что часть S , принадлежащая Р , состоит только из истинных S ( n ). Почему это так? Понятно, что если любое конкретное S ( n ) доказуемо, то оно должно быть верным (ведь наша формальная система была выбрана так, чтобы иметь «смысл»!), и поэтому часть S , лежащая в Р , должна состоять исключительно из справедливыхутверждений S ( n ). Более того, ни одно верное утверждение S ( n ) не должно лежать вне Р , ибо, если Т _n ( n ) останавливается, то мы можем отыскать доказательство этому в рамках нашей системы [82] .

82

''Доказательство могло бы, в действительности, состоять из последовательности шагов, которые отражали бы действие машины, продолжающееся до ее остановки. Доказательство завершалось бы, как только машина остановится.

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

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