Чтение онлайн

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

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

В действительности теорема Геделя носит более частный характер, поскольку от формальной системы того типа, который рассматривал Гедель, требовалась адекватность по отношению к арифметическим утверждениям, а не математическим утверждениям вообще. Можем ли мы устроить так, чтобы все необходимые операции машины Тьюринга выполнялись только при помощи арифметики? Или, иными словами, могут ли все вычислимые функции натуральных чисел (т. е. рекурсивные, или алгоритмические функции — результаты действия машины Тьюринга) быть выражены в терминах обычной арифметики? На самом деле это так, хотя и не совсем. Нам понадобится одна дополнительная операция, которую мы добавим в систему стандартных правил арифметики и логики (включая кванторы E к.с. и A к.о. ). Эта операция просто выбирает «наименьшее натуральное число такое, что K ( х ) имеет значение „истина“», где К — заданная арифметически вычислимая функция исчисления высказываний, для которой предполагается существованиетакого числа, т. е. что

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… }, равно как и пустое множество o = {}. Нас будут интересовать только вопросы вычислимости, скажем: «Какие множества натуральных чисел могут быть сгенерированы с помощью алгоритма, а какие — нет?»

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