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

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

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