или же нет? В обычных математических терминах все, что мы можем сказать на сегодняшний день, это то, что они либо существуют, либо нет - и мы не знаем, какая из этих возможностей верна! Казалось бы, вполне безобидное утверждение. Однако правомерность утверждения "последовательность из двадцати семерок либо существует где-то в дробной части числа π, либо нет" будет отвергаться интуиционистами до тех пор, пока не получится установить (некоторым приемлемым с точки зрения интуиционизма конструктивным образом), что такая последовательность действительно существует, или же что такой последовательности нет! Прямого подсчета было бы достаточно для того, чтобы доказать, что данная последовательность действительно существует в дробной части π, но для доказательства невозможности ее существования потребовалась бы математическая теорема. Пока ни один компьютер не в состоянии просчитать дробную часть π с такой точностью, чтобы определить наличие там искомой последовательности. Можно было бы, с вероятностной точки зрения, предположить ее существование, однако, даже если бы компьютер вычислял каждую секунду, скажем, по 10 цифр, то для нахождения этой последовательности потребовалось бы предположительно от ста до тысячи лет. Мне представляется гораздо более вероятным, что существование такой последовательности будет однажды установлено скорее математически, чем путем прямых вычислений (возможно, как побочный результат более глобального и интересного исследования) - хотя не исключено, что это будет сделано неприемлемым для интуиционистов способом!
Данная проблема не имеет для математики особого значения и приведена лишь как наглядный пример. Брауэр, с позиций радикального интуиционизма, сказал бы, что в настоящее время утверждение "где-то в дробной части числа π существует двадцать последовательных семерок" не является ни справедливым, ни ложным. Если когда-либо в дальнейшем будет установлен конкретный результат - посредством вычислений или путем (интуиционистского) математического доказательства - то тогда утверждение станет "истинным" или "ложным", соответственно. Сходный пример представляет собой и "последняя теорема Ферма". Вновь, согласно крайнему интуиционизму Брауэра, это утверждение не может быть сегодня признано ни ложным, ни истинным, но возможно, что его значение будет определено в будущем. По-моему, такая субъективность и "конъюнктурность" понятия математической истины просто неприемлема. Действительно, вопрос, будет ли - а если будет, то когда - официально признана "доказанность" некоторого математического результата, является весьма субъективным. Математическая истина не должна подчиняться такому "общественно-зависимому" критерию. Помимо этого, опираться на понятие математической истины, зависящее от времени - это, мягко говоря, наиболее неудобный и неудовлетворительный подход для математики, которую предполагается использовать для достоверного описания физического мира. Не все интуиционисты придерживаются таких радикальных взглядов, как Брауэр. И все же точка зрения интуиционистов является, бесспорно, крайне неудобной, даже когда она родственна идеям конструктивизма. Немногие современные математики строго исповедуют чистый интуиционизм, даже если бы единственной причиной этого была бы его ограниченность относительно типов математических рассуждений, которые он позволяет использовать.
Я коротко описал три основных направления в современной математической философии: формализм, платонизм и интуиционизм. Я не скрываю, что практически целиком отдаю предпочтение платонистской точке зрения, согласно которой математическая истина абсолютна и вечна, является внешней по отношению к любой теории и не базируется ни на каком "рукотворном" критерии; а математические объекты обладают свойством собственного вечного существования, не зависящего ни от человеческого общества, ни от конкретного физического объекта. Я попытался привести аргументы в пользу этой точки зрения в этом и предыдущем разделах, а также в конце третьей главы. Я надеюсь, что читатель готов следовать за мной и далее в этих рассуждениях, которые будут очень важны для понимания многих положений в дальнейшем.
Теоремы геделевского типа как следствие результатов, полученных Тьюрингом
В моем изложении теоремы Геделя я опустил многие детали и к тому же оставил в стороне то, что относилось к неразрешимость вопроса о непротиворечивости системы аксиом и было исторически наиболее важной частью его доказательства. Моя задача состояла не в том, чтобы акцентировать внимание на "проблеме доказуемости непротиворечивости аксиом", столь важной для Гильберта и его современников; я стремился показать, что специфическое утверждение Геделя - которое нельзя ни подтвердить, ни опровергнуть исходя из аксиом и правил вывода рассматриваемой формальной системы - оказывается с очевидностью верным, если опираться в наших рассуждениях на интуитивное понимание смысла применяемых процедур.
Я уже упоминал, что Тьюринг разработал свое доказательство неразрешимости проблемы остановки после изучения работ Геделя. Оба доказательства имеют много общего и, естественно, основные положения из результатов Геделя могут быть непосредственно получены путем использования процедуры Тьюринга. Давайте посмотрим, как это происходит, и как при этом можно несколько иным образом взглянуть на то, что осталось за кулисами теоремы Геделя.
Непременное свойство формальной математической системы заключается в существовании вычислимого способа решить, является ли некоторая строка символов доказательством соответствующего математического утверждения или нет. Весь смысл формализации понятия математического доказательства в конечном счете сводится к тому, чтобы не требовалось никакого дополнительного суждения о состоятельности того или иного типа рассуждений. Необходимо обеспечить возможность проверять полностью механическим и заранее определенным способом, что предполагаемое доказательство и в самом деле является таковым - то есть должен существовать алгоритм для проверки доказательств. С другой стороны, мы не требуем существования алгоритмической процедуры нахождения доказательств истинности (или ложности) предлагаемых математических утверждений.
Как оказывается, алгоритм отыскания доказательства внутри произвольной формальной системы присутствует всегда, если только система допускает какое-нибудь доказательство. Действительно, мы прежде всего должны предполагать, что наша система формулируется на некотором языке символов, который можно выразить в терминах некоторого конечного "алфавита" символов. Как и ранее, давайте упорядочим наши строки символов лексикографически, что, как мы помним, означает расставление в алфавитном порядке строк каждой определенной длины, где все строчки единичной длины идут первыми, за ними следуют (также упорядоченные) строки из двух символов, потом - из трех, и так далее (см. прим. 72 подглавы "Теорема Геделя").
Тогда мы будем иметь корректно построенные и пронумерованные в соответствии с лексикографической схемой доказательства. Располагая нашим списком доказательств, мы одновременно имеем и перечень всех теорем нашей формальной системы, поскольку теорема - это утверждение, которое стоит в последней строчке списка корректно построенных доказательств. Подобный перечень полностью проверяется непосредственными вычислениями: ведь мы можем рассматривать все строки символов системы - независимо от того, имеют они смысл как доказательства или нет - и начать тестировать нашим алгоритмом первую строчку, чтобы понять, является ли она доказательством, и отбросить ее, если нет; затем мы подобным же образом тестируем вторую строчку и исключаем ее, если и она не является доказательством; потом следует третья строчка, четвертая и так далее. Посредством этого мы в конце концов достигнем строки, содержащей доказательство, если таковая имеется в нашем списке.
Таким образом, если бы Гильберту удалось отыскать свою математическую систему - систему аксиом и правил вывода, достаточно мощную, чтобы позволить решать, путем формального доказательства, вопрос о справедливости или ложности любого математического утверждения, корректно сформулированного в рамках системы, - то тогда существовал бы общий алгоритмический метод выяснения истинности любого такого рассуждения. Почему это так? Потому что, если мы при помощи процедуры, описанной выше, находим искомое утверждение как последнюю строчку некоторого доказательства, то это утверждение автоматически считается доказанным. Если же, напротив, мы находим последнюю строчку, содержащую отрицание нашего утверждения, то мы тем самым доказываем его ложность. Если бы схема Гильберта была полной, то либо одна, либо другая возможность обязательно имела бы место (и если бы система была непротиворечивой, то обе возможности никогда бы не могли быть реализованы одновременно). То есть наша механическая процедура всегда бы прерывалась на некотором шаге и мы бы имели универсальный алгоритм для доказательства истинности или ложности всех утверждений системы. Это находилось бы в противоречии с результатами Тьюринга, изложенными во второй главе, согласно которым не существует общего алгоритма для доказательства математических утверждений. И, как следствие, мы доказали теорему Геделя о том, что ни одна система наподобие задуманной Гильбертом не может быть полной в обсуждаемом нами смысле.
В действительности теорема Геделя носит более частный характер, поскольку от формальной системы того типа, который рассматривал Гедель, требовалась адекватность по отношению к арифметическим утверждениям, а не математическим утверждениям вообще. Можем ли мы устроить так, чтобы все необходимые операции машины Тьюринга выполнялись только при помощи арифметики? Или, иными словами, могут ли все вычислимые функции натуральных чисел (т. е. рекурсивные, или алгоритмические функции - результаты действия машины Тьюринга) быть выражены в терминах обычной арифметики? На самом деле это так, хотя и не совсем. Нам понадобится одна дополнительная операция, которую мы добавим в систему стандартных правил арифметики и логики (включая кванторы Eк.с. и Aк.о.). Эта операция просто выбирает "наименьшее натуральное число такое, что K(х) имеет значение "истина"", где К() - заданная арифметически вычислимая функция исчисления высказываний, для которой предполагается существование такого числа, т. е. что
Eк.с.x[K(х)] является истинным. (Если бы такого числа не было, то наша операция повторялась бы "бесконечно"), стараясь обнаружить несуществующее x.) В любом случае, предшествующие рассуждения показывают, что, исходя из результатов Тьюринга, программа Гильберта по сведению целых разделов математики к вычислениям в рамках некоторой формальной системы - невыполнима.
Как оказывается, эта процедура не может с очевидностью установить, что мы имеем утверждение Геделя (наподобие Pk(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… }, равно как и пустое множество ø = {}. Нас будут интересовать только вопросы вычислимости, скажем: "Какие множества натуральных чисел могут быть сгенерированы с помощью алгоритма, а какие - нет?"
Чтобы сформулировать такой вопрос, мы можем считать, что каждое отдельное число n обозначает определенную строчку символов некоторой формальной системы.
Это будет n-я строка символов, скажем, Qn, согласно заданному в системе лексикографическому порядку ("синтаксически корректных") утверждений. Тогда каждое натуральное число будет представлять некое утверждение. При этом множество всех утверждений формальной системы соответствует всему множеству натуральных чисел; а, допустим, теоремы этой системы будут составлять некоторое меньшее множество натуральных чисел, скажем, множество Р. Однако детали произвольной системы нумерации утверждений для нас несущественны. Все, что нам потребуется для установления соответствия между натуральными числами и утверждениями - это заданный алгоритм получения каждого утверждения Qn (записанного должным образом в символических обозначениях) из отвечающего ему натурального числа n; и другой алгоритм для получения n из Qn. Имея эти алгоритмы в своем распоряжении, мы вольны идентифицировать множество натуральных чисел с множеством утверждений конкретной формальной системы.
Давайте выберем формальную систему достаточно непротиворечивую и широкую для того, чтобы включать в себя все действия всех машин Тьюринга - и, более того, "имеющую смысл" с учетом требования "самоочевидной справедливости" ее аксиом и правил вывода. Далее, пусть ряд утверждений Q0, Q1, Q2…. формальной системы имеет доказательства внутри системы. Эти "доказуемые" утверждения будут иметь номера, которые составляют некоторое множество в 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 четным, квадратом натурального числа или простым числом, соответственно. Это дает нам алгоритм для построения обоих множеств, поскольку мы можем перебирать все натуральные числа и для каждого из них решать, принадлежит ли оно к определенному множеству или же к его дополнению. Множество, которое обладает свойством рекурсивной нумеруемости вместе со своим дополнением, называется рекурсивным. Очевидно, что дополнительное по отношению к рекурсивному множество также будет рекурсивным.