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

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

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