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

Автор книги: Роджер Пенроуз

сообщить о нарушении

Текущая страница: 12 (всего у книги 47 страниц)

Платонизм или интуиционизм?

Я указал две противостоящие друг другу школы математической философии, решительно причисляя себя более к платонистскому, нежели к формалистскому воззрению. В действительности же я применил довольно упрощенный подход при их разделении. Существует множество тонкостей, которые можно было бы принять в расчет. Например, в рамках платонизма можно поставить вопрос о том, существуют ли в реальности объекты математической мысли или это только лишь понятие «математической истины», которое является абсолютным. Я решил не обсуждать здесь подобные различия. В моем представлении абсолютность математической истины и платонистское существование математических понятий, по существу, тождественны. «Существование», которое должно быть приписано множеству Мандельброта, к примеру, есть свойство его абсолютной природы. Принадлежит ли точка плоскости Аргана множеству Мандельброта или нет – вопрос абсолютный, не зависящий от математика или компьютера, которые его исследуют. Эта «независимость-от-математика» множества Мандельброта и обеспечивает ему платонистское существование. Более того, наиболее тонкие детали этого множества лежат за пределами того, что можно достигнуть с помощью компьютера. Эти устройства способны только аппроксимировать структуры, имеющие свое, более глубокое и «не зависящее-от-компьютера», существование. Я, однако, готов согласиться с тем, что имеются и прочие разумные точки зрения, с которых можно исследовать этот вопрос. Но здесь нам нет необходимости придавать значение этим различиям.

Есть также отличие в том, насколько далеко в своем платонизме готов зайти человек, провозглашающий свою принадлежность к этой школе. Сам Гедель был глубоко убежденным платонистом. Математические выражения, которые я до сих пор рассматривал, являют собой довольно «мягкие» примеры того, что может встретиться в этом направлении! [77]77
  Континуум-гипотеза, которая упоминалась в главе 3, (конец подглавы «Сколько же всего действительных чисел?», и из которой следует, что С=  N ₁), является наиболее «экстремальным» математическим утверждением, которое здесь встречается (хотя часто рассматриваются и куда более «экстремальные» рассуждения). Континуум-гипотеза интересна еще и потому, что сам Гедель, совместно с Полом Дж. Коэном, показал, что эта гипотеза в действительности не зависитот стандартных аксиом и правил теории множеств. Таким образом, отношение любого математика к континуум-гипотезе позволяет причислить его к сторонникам либо формалистской, либо платонистской точки зрения. Для формалиста данная гипотеза будет «недоказуемой», поскольку ее справедливость не может быть установлена или опровергнута, если опираться на стандартную (построенную Цермело и Френкелем) формальную систему, и, значит, не «имеет смысла» называть ее ни «истинной», ни «ложной». Однако, для убежденного платониста эта гипотеза является либо истинной, либо ложной, хотя какой именно – это можно установить только путем рассуждений некоторого нового типа, идущих еще дальше, чем использование геделевских утверждений для формальной системы Цермело – Френкеля. (Коэн [1966] сам предложил принцип рефлексии, который позволяет показать, что континуум-гипотеза – «с очевидностью ложна»!)


[Закрыть]. Вполне возможны и более «запутанные» выражения, особенно в теории множеств. Когда рассматриваются все мыслимые ответвления этой теории, то порой возникают множества столь громадные и причудливо сконструированные, что даже такой весьма убежденный платонист, как я, может начать сомневаться в абсолютности их существования (или, напротив, несуществования) [78]78
  Живое и не слишком насыщенное техническими деталями изложение этой темы можно найти у Ракера [1984].


[Закрыть]. Может наступить момент, когда определения множеств становятся настолько сложными и концептуально шаткими, что вопрос об истинности или ложности относящихся к ним математических выражений становится скорее субъективным и зависящим от мнения исследователя, нежели «ниспосланным свыше». Готов ли иной математик безоглядно следовать вместе с Геделем путем платонизма, провозглашая истинность или ложность математических выражений, оперирующих подобными огромными множествами, всегда абсолютными (или «платонистскими») по своей природе; или же он, не заходя слишком далеко, будет говорить об абсолютности этих понятий лишь в том случае, если множества окажутся не слишком велики и довольно конструктивны. Ответ на этот вопрос не имеет большого отношения к нашей дискуссии. Множества (конечные или бесконечные), которые будут иметь для нас значение, по меркам вышеупомянутых множеств выглядят до смешного маленькими! Так что различия между разными платонистскими течениями нас волновать не должны.

Имеются, однако, и иные точки зрения в математике, такие как интуиционизм (и финитизм ), которые, впадая в противоположную крайность, отказываются признавать существование каких бы то ни было бесконечных множеств [79]79
  Интуиционизм был назван так потому, что ему предназначалось служить отражением человеческой мысли.


[Закрыть]. Интуиционизм был основан в 1924 году датским математиком Лейтзеном Э. Брауэром как альтернативный ответ – отличный от предлагаемого формализмом – на парадоксы (типа расселовского), которые могут возникать там, где бесконечные множества используются слишком вольно в математических рассуждениях. Зачатки этого подхода прослеживаются еще во времена Аристотеля, который, будучи учеником Платона, тем не менее отвергал его взгляды на абсолютное существование математических сущностей и возможность рассмотрения бесконечных множеств. Согласно интуиционизму, существование множества (бесконечного, равно как, впрочем, и конечного) не может признаваться как свойство, изначально ему присущее, а только лишь как функция правил, по которым оно организовано.

Характерная черта интуиционизма Брауэра состоит в отрицании закона «исключенного третьего». Этот закон говорит о том, что отрицание ложности некоторого выражения эквивалентно утверждению истинности этого выражения. (Или в принятой символике: ~ ( ~ P ) <=> P , отношение, которое нам уже встречалось ранее.) Наверное, Аристотель был бы очень недоволен, столкнувшись с отрицанием настолько логически «очевидного» факта! С общепринятых позиций здравого смысла закон «исключенного третьего» может рассматриваться как самоочевидная истина: если утверждение о том, что нечто ложно, само неверно, то это нечто должно быть непременно справедливым! (На этом законе основана математическая процедура « доказательства от противного», упомянутой в прим. 53 подглавы «Неразрешимость проблемы Гильберта») Но интуиционисты считают допустимым отвергать справедливость этого закона. Основная причина здесь в том, что они занимают иную позицию по отношению к понятию существования, требуя, чтобы перед признанием существования математического объекта предъявлялось его конкретное (мысленное) построение. То есть, для интуиционалиста «существование» означает «конструктивное существование». В математическом доказательстве, использующем принцип «доказательства от противного», сперва выдвигается некая гипотеза, ложность которой затем устанавливается путем обнаружения противоречий, к которым приводят следствия из этой гипотезы. Эта гипотеза может принимать форму утверждения о том, что математический объект с требуемыми свойствами не существует. Когда это приводит к противоречию, то в обычной математикеделается вывод о том, что данный объект да, существует. Но подобное доказательство, само по себе, не содержит руководства для построениятакого объекта. Такое существование для интуициониста существованием отнюдь не является; и именно на этом основании они отказываются признавать закон «исключенного третьего» и процедуру «доказательства от противного». Сам Брауэр был совершенно неудовлетворен таким неконструктивным подходом к понятию существования [80]80
  Сам Брауэр начал размышлять в этом направлении, в частности, потому, что очень придирчиво и болезненно относился к «неконструктивности» доказательства своей теоремы из области топологии, «теоремы Брауэра о неподвижной точке». Эта теорема утверждает, что, если вы возьмете круг – то есть окружность вместе со всеми точками внутри нее – и будете непрерывно двигать его внутри области, где он находился изначально, то найдется по крайней мере одна точка круга, – называемая неподвижной точкой, – которая окажется точно там же, откуда она начала движение. Не ясно, где именно располагается эта точка, и может ли их быть несколько – теорема говорит только о существованиитакой точки. (Среди математических теорем существования, эта, на самом деле, носит довольно «конструктивный» характер. Примеры теорем существования более высокой степени неконструктивности ― это теоремы, зависящие от так называемой «аксиомы выбора» или «леммы Цорна» (см. Коэн [1966], Ракер [1984]).) Трудность в случае Брауэра была аналогична той, что возникает в следующей задаче: найти точки, в которых f обращается в нуль, если известно, что f – действительная непрерывная функция действительной переменной, которая принимает как положительные, так и отрицательные значения. Стандартная процедура заключается в последовательном делении пополам отрезка, на котором функция меняет свой знак; но решение о том, какое именно промежуточное значение принимает функция (положительное, отрицательное или нулевое), может оказаться неконструктивным в том смысле, которого требует Брауэр.


[Закрыть]. Без указания реально осуществимого метода построения, говорил он, такая теория существования будет бессмысленной. В логике Брауэра нельзя сделать заключение о существовании объекта, исходя из ложности утверждения о его несуществовании!

По моему мнению, несмотря на похвальное стремление искать «конструктивное» решение вопроса о математическом существовании, интуиционизм, исповедуемый Брауэром, все же является слишком радикальным. Брауэр впервые опубликовал свои идеи в 1924 году, более чем за десять лет до работ Тьюринга и Черча. Теперь, когда понятие конструктивности – в терминах теории Тьюринга о вычислимости – может изучаться в общепринятых рамках математической философии, уже нет необходимости впадать в крайности, как к тому нас призывает Брауэр. Мы можем исследовать конструктивность как самостоятельный предмет, отдельный от вопроса математического существования. Если мы последуем путем интуиционизма, то будем вынуждены отказаться от использования очень мощных приемов доказательства в математике, заметно ограничивая и лишая силы сам предмет.

Я не хочу излишне подробно останавливаться на разнообразных трудностях и кажущихся абсурдностях, к которым приводит интуиционистский подход; но упоминание некоторых проблем может оказаться полезным. Один из примеров, к которому часто обращается для иллюстрации Брауэр, касается дробной части числа π :

3,14152653589793….

Существует ли двадцать последовательных семерок где-нибудь в этой части, т. е.:

π = 3,14152653…

…77777777777777777777…,

или же нет? В обычных математических терминах все, что мы можем сказать на сегодняшний день, это то, что они либо существуют, либо нет – и мы не знаем, какая из этих возможностей верна! Казалось бы, вполне безобидное утверждение. Однако правомерность утверждения «последовательность из двадцати семерок либо существует где-то в дробной части числа  π , либо нет» будет отвергаться интуиционистами до тех пор, пока не получится установить (некоторым приемлемым с точки зрения интуиционизма конструктивным образом), что такая последовательность действительно существует, или же что такой последовательности нет! Прямого подсчета было бы достаточно для того, чтобы доказать, что данная последовательность действительно существует в дробной части π , но для доказательства невозможности ее существования потребовалась бы математическая теорема. Пока ни один компьютер не в состоянии просчитать дробную часть π с такой точностью, чтобы определить наличие там искомой последовательности. Можно было бы, с вероятностной точки зрения, предположить ее существование, однако, даже если бы компьютер вычислял каждую секунду, скажем, по 10 ¹⁰цифр, то для нахождения этой последовательности потребовалось бы предположительно от ста до тысячи лет. Мне представляется гораздо более вероятным, что существование такой последовательности будет однажды установлено скорее математически, чем путем прямых вычислений (возможно, как побочный результат более глобального и интересного исследования) – хотя не исключено, что это будет сделано неприемлемым для интуиционистов способом!

Данная проблема не имеет для математики особого значения и приведена лишь как наглядный пример. Брауэр, с позиций радикального интуиционизма, сказал бы, что в настоящее время утверждение «где-то в дробной части числа π существует двадцать последовательных семерок» не является ни справедливым, ни ложным. Если когда-либо в дальнейшем будет установлен конкретный результат – посредством вычислений или путем (интуиционистского) математического доказательства – то тогда утверждение станет «истинным» или «ложным», соответственно. Сходный пример представляет собой и «последняя теорема Ферма». Вновь, согласно крайнему интуиционизму Брауэра, это утверждение не может быть сегодня признано ни ложным, ни истинным, но возможно, что его значение будет определено в будущем. По-моему, такая субъективность и «конъюнктурность» понятия математической истины просто неприемлема. Действительно, вопрос, будет ли – а если будет, то когда – официально признана «доказанность» некоторого математического результата, является весьма субъективным. Математическая истина не должна подчиняться такому «общественно-зависимому» критерию. Помимо этого, опираться на понятие математической истины, зависящее от времени – это, мягко говоря, наиболее неудобный и неудовлетворительный подход для математики, которую предполагается использовать для достоверного описания физического мира. Не все интуиционисты придерживаются таких радикальных взглядов, как Брауэр. И все же точка зрения интуиционистов является, бесспорно, крайне неудобной, даже когда она родственна идеям конструктивизма. Немногие современные математики строго исповедуют чистый интуиционизм, даже если бы единственной причиной этого была бы его ограниченность относительно типов математических рассуждений, которые он позволяет использовать.

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

Теоремы геделевского типа как следствие результатов, полученных Тьюрингом

В моем изложении теоремы Геделя я опустил многие детали и к тому же оставил в стороне то, что относилось к неразрешимость вопроса о непротиворечивости системы аксиом и было исторически наиболее важной частью его доказательства. Моя задача состояла не в том, чтобы акцентировать внимание на «проблеме доказуемости непротиворечивости аксиом», столь важной для Гильберта и его современников; я стремился показать, что специфическое утверждение Геделя – которое нельзя ни подтвердить, ни опровергнуть исходя из аксиом и правил вывода рассматриваемой формальной системы – оказывается с очевидностью верным, если опираться в наших рассуждениях на интуитивное понимание смысла применяемых процедур.

Я уже упоминал, что Тьюринг разработал свое доказательство неразрешимости проблемы остановки после изучения работ Геделя. Оба доказательства имеют много общего и, естественно, основные положения из результатов Геделя могут быть непосредственно получены путем использования процедуры Тьюринга. Давайте посмотрим, как это происходит, и как при этом можно несколько иным образом взглянуть на то, что осталось за кулисами теоремы Геделя.

Непременное свойство формальной математической системы заключается в существовании вычислимого способа решить, является ли некоторая строка символов доказательством соответствующего математического утверждения или нет. Весь смысл формализации понятия математического доказательства в конечном счете сводится к тому, чтобы не требовалось никакого дополнительного суждения о состоятельности того или иного типа рассуждений. Необходимо обеспечить возможность проверять полностью механическим и заранее определенным способом, что предполагаемое доказательство и в самом деле является таковым – то есть должен существовать алгоритм для проверки доказательств. С другой стороны, мы не требуем существования алгоритмической процедуры нахождениядоказательств истинности (или ложности) предлагаемых математических утверждений.

Как оказывается, алгоритм отыскания доказательства внутри произвольной формальной системы присутствует всегда, если только система допускает какое-нибудь доказательство. Действительно, мы прежде всего должны предполагать, что наша система формулируется на некотором языке символов, который можно выразить в терминах некоторого конечного «алфавита» символов. Как и ранее, давайте упорядочим наши строки символов лексикографически, что, как мы помним, означает расставление в алфавитном порядке строк каждой определенной длины, где все строчки единичной длины идут первыми, за ними следуют (также упорядоченные) строки из двух символов, потом – из трех, и так далее (см. прим. 72 подглавы «Теорема Геделя»).

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

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

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

E _к.с. x [ K ( х )] является истинным. (Если бы такого числа не было, то наша операция повторялась бы «бесконечно» [81]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… }, равно как и пустое множество ø = {}. Нас будут интересовать только вопросы вычислимости, скажем: «Какие множества натуральных чисел могут быть сгенерированы с помощью алгоритма, а какие – нет?»

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


[Закрыть].

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

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

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