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

Может ли возникнуть такая ситуация в реальности? Есть ли и вправду рекурсивно нумеруемые множества, не являющиеся рекурсивными? А как насчет множества Р? Имеет ли это множество свойство рекурсивности? Мы знаем, что оно рекурсивно нумеруемо, так что нам остается только выяснить, будет ли также дополнительное к нему множество обладать этим свойством. Оказывается, что нет! Как мы можем сделать такой вывод? А давайте вспомним, что наряду с остальными операциями в нашей формальной системе разрешены и действия машин Тьюринга. Если мы обозначим 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].

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

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

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

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

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

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