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

Программа Гильберта для математики

Что есть истина? Как мы составляем наши суждения о том, что в мире является справедливым, верным, а что — нет? Следуем ли мы некоторому алгоритму, которому отдается предпочтение среди прочих, менее эффективных, в процессе всемогущего естественного отбора? Или же возможен некий иной путь — не алгоритмизированный, а основанный на особой проницательности, интуитивный, инстинктивный — позволяющий угадывать правду? Это представляется нелегким вопросом. Наши суждения зависят от сложных взаимосвязанных комбинаций данных, поставляемых органами чувств, и наших размышлений и догадок. Более того, во многих реальных ситуациях не может существовать единого мнения по поводу того, что на самом деле истинно, а что — ложно. Чтобы упростить задачу, рассмотрим только лишь математическую истину. Как мы формируем суждения — а может, даже и наши «стопроцентно верные» знания — при ответе на вопросы из области математики? Там уж, по крайней мере, все должно быть не так размыто, очерчено более ясно. Там не может возникать вопросов об истинности — или все-таки может? Что же, в конце концов, есть математическая истина?

Вопрос об этой истине возник не сегодня, он уходит корнями в античность, к греческим философам и математикам — и, несомненно, еще дальше, в глубь веков. Однако, несколько великих открытий и поразительных прозрений здесь были сделаны не далее как в XX столетии. Эти новые достижения заслуживают того, чтобы постараться их понять. Они носят фундаментальный характер и непосредственно касаются вопроса о том, являются ли наши мыслительные процессы полностью алгоритмизированными по своей природе или нет. Четко разобраться в этом — задача, имеющая для нас весьма важное значение.

В последней части XIX века математика шагнула далеко вперед в результате развития все более и более мощных методов математического доказательства. (Давид Гильберт и Георг Кантор, с которыми мы познакомились ранее, и великий французский математик Анри Пуанкаре, с которым нам еще предстоит встретиться, шли во главе этих разработок.) Как следствие, математики стали обретать уверенность в том, что применение этих методов приведет к успеху. Многие из таких методов основаны на рассмотрении множеств [68]с бесконечным числом членов, и доказательства часто оказывались осуществимы благодаря именно тому, что такое множество можно было рассматривать как реальный «объект» — завершенное единое целое, существующее не только в абстракции. Многие из этих идей родились из в высшей степени оригинальной концепции Кантора о бесконечных числах, которую он развил, последовательно используя бесконечные множества. (Мы кратко ознакомились с ними в предыдущей главе.)

Однако эта уверенность пошатнулась, когда в 1902 году английский логик и философ Бертран Рассел придумал свой знаменитый парадокс (который предвидел и сам Кантор и который выводился непосредственно из его диагонального процесса). Чтобы понять доводы Рассела, мы сначала должны хотя бы немного почувствовать, как можно представить множество в виде единого целого. Давайте представим себе множество, характеризуемое некоторым (общим) свойством. Например, набор красных предметов может быть охарактеризован словом «краснота» как его определяющим свойством: нечто принадлежит этому множеству тогда и только тогда, когда это обладает «краснотой» (имеет красный цвет). Это позволит нам «перевернуть» точку зрения и трактовать свойство как единичный объект, который будет состоять из всего множества вещей, обладающих данным свойством. При таком рассмотрении «краснота» эквивалентна множеству всех красных предметов. (При этом мы можем предполагать существование «там вовне» и других множеств, члены которых не могут быть охарактеризованы подобным простым свойством.)

Идея формулировки понятий в терминах множеств послужила основой для процедуры, предложенной в 1884 году влиятельным немецким логиком Готтлибом Фреге, которая позволяла определять числа через множества. К примеру, что мы понимаем под числом 3 ? Мы знаем, в чем заключается «тройственность», но что есть число 3 само по себе? Очевидно, что «тройственность» есть свойство наборов объектов, т. е. свойство множеств: некоторое множество обладает данным свойством тогда и только тогда, когда это множество состоит из трех членов. Этим свойством характеризуется, скажем, тройка призеров-медалистов некоторой Олимпиады. Равно как и набор шин к трехколесному велосипеду, или листья на одном стебельке обычного клевера, или множество всех решений уравнения x ³ — 6х ² + 11x — 6 = 0 . Как же можно тогда определить по Фреге само число 3 ? Согласно Фреге, 3 — это множество множеств, а именно, всех множеств, имеющих свойство «тройственности» [69]. Таким образом, множество содержит три члена тогда и только тогда, когда оно принадлежит множеству 3 по Фреге.

Может показаться, что мы попадаем в замкнутый круг, но в действительности это совсем не так. Мы можем определить числа в общем случае как совокупности всевозможных эквивалентных множеств, где говоря «эквивалентные», мы понимаем «состоящие из элементов, которые могут быть попарно сопоставлены друг другу» (или, в более привычной терминологии, «имеющих одинаковое число элементов»). Тогда число 3 будет одной из этих совокупностей множеств, которая содержит в себе в качестве члена множество, состоящее, скажем, из яблока, апельсина и груши. Обратите внимание, что это принципиально отличается от определения « 3 », данного Черчем (см. гл.2 «Лямбда-исчисление Черча»). Существуют также и другие определения, причем более популярные в наши дни.

Вернемся теперь к парадоксу Рассела. В чем он заключается? В нем рассматривается множество R , определенное следующим образом:

R есть множество множеств, которые не являются членами самих себя.

Таким образом, R есть набор множеств X , отвечающих следующему условию: среди членов множества X не должно быть самого X .

Не является ли абсурдным предполагать, что множество в действительности может быть членом самого себя? Ничуть. Рассмотрим, к примеру, множество I , состоящее из бесконечных множеств (множеств с бесконечным числом членов). С очевидностью, существует бесконечное число различных бесконечных множеств, и само множество I , таким образом, является бесконечным. И, таким образом, оно, действительно, принадлежит самому себе! Но как же, в таком случае, рассуждения Рассела дают нам парадоксальное утверждение? Давайте спросим: является ли множество Рассела R членом самого себя или нет? Если нет, то оно должно принадлежать себе, ибо R состоит как раз из таких множеств, которые не являются членами самих себя. То есть, в конечном счете, R принадлежит R — противоречие! С другой стороны, если R есть член самого себя, то, поскольку «самое себя» — это R , оно в то же время принадлежит множеству, члены которого, по определению, не могут быть составляющими самих себя, т. е. все-таки не принадлежит самому себе — и вновь противоречие! [70]

Этот парадоксальный вывод не был праздной игрой ума: Рассел использовал — хотя и в крайней форме — тот же тип весьма общих теоретико-множественных методов, которые математики начинали использовать в то время для своих доказательств. Становилось очевидным, что казавшаяся незыблемой почва ускользает из-под ног, и поэтому необходимо было как можно точнее определить, какие рассуждения считать допустимыми. Ясно было, что такие рассуждения должны быть свободны от внутренних противоречий, и что утверждения, которые будут выводиться с их помощью как следствия из априори верных посылок, должны быть также верными. Рассел, совместно со своим коллегой Альфредом Нортом Уайтхедом, взялся за развитие такой полностью формализованной системы аксиом и правил вывода, на язык которой стало бы возможным перевести все виды корректных математических рассуждений. Все правила подвергались тщательному отбору, дабы избежать «ложных» путей рассуждений, могущих привести к парадоксам, подобным упомянутому выше. Однако схема, появившаяся на свет в результате этих усилий, была очень громоздка и оказалась весьма ограниченной по диапазону различных типов математических рассуждений, которые она охватывала. Великий математик Давид Гильберт (которого мы впервые встретили в главе 2) задался целью создать более практичную и универсальную систему. В нее должны были войти все типы математических рассуждений из всех областей математики. Более того, Гильберт стремился сделать возможным строгое доказательство отсутствия противоречий в своей схеме. Тогда математика раз и навсегда смогла бы встать на прочную и неколебимую основу.

Однако надежды Гильберта и его последователей были перечеркнуты, когда в 1931 году блестящий австрийский логик математики Курт Гедель выдвинул поразительную теорему, которая до основания разрушала программу Гильберта. Гедель показал, что любая подобная точная («формальная») система аксиом и правил вывода, если только она достаточна широка, чтобы содержать в себе описания простых арифметических теорем (как, например, «последняя теорема Ферма», рассмотренная в главе 2), и если она свободна от противоречий — то такая система должна включать утверждения, которые не являются ни доказуемыми, ни недоказуемыми в рамках формализма данной системы. Истинность таких «неразрешимых» утверждений, следовательно, не может быть выяснена с помощью методов, допускаемых самой системой. Более того, Гедель смог показать, что даже утверждение о непротиворечивости системы аксиом, будучи переведенным в форму соответствующей теоремы, само по себе является «неразрешимым». Для нас будет очень важным понять природу этой неразрешимости. Тогда мы увидим, почему выводы Геделя опровергали самое основание программы Гильберта. Мы также увидим, каким образом они дают нам возможность, воспользовавшись интуицией, выходить за пределы любой рассматриваемой формализованной математической системы. Это понимание будет решающим для того, чтобы, в свою очередь, лучше понять обсуждаемое далее.

Формальные математические системы

Необходимо будет несколько уточнить, что мы понимаем под «формальными математическими системами аксиом и правил вывода». Мы должны предположить наличие некоторого алфавита символов, через которые будут записываться математические выражения. Эти символы в обязательном порядке должны быть адекватны для записи натуральных чисел с тем, чтобы в нашу систему могла быть включена «арифметика». По желанию, мы можем использовать общепринятую арабскую запись 0, 1, 2, 3…, 9, 10, 11, 12… хотя при этом конкретные выражения для правил вывода становятся несколько более сложными, чем требуется. Гораздо более простые выражения получаются, скажем, при использовании записи вида 0, 01, 011, 0111, 01111… для обозначения последовательности натуральных чисел (или, в качестве компромисса, мы могли бы использовать двоичную запись). Однако, поскольку это могло бы стать источником разночтений в дальнейших рассуждениях, я буду для простоты придерживаться обычной арабской записи независимо от способа обозначения, которая может на самом деле использоваться в данной системе. Нам мог бы понадобиться символ «пробел» для разделения различных «слов» или «чисел» в нашей системе, но, так как это тоже может вызвать путаницу, то мы будем по мере необходимости использовать для этих целей просто запятую (,). Произвольные («переменные») натуральные числа (равно как и целые, рациональные и т. д.; но давайте здесь ограничимся натуральными) мы станем обозначать буквами, например, t , u , v , ω , х , у , z , t' , t'' , t''' и т. п. Штрихованные буквы t' , t'', … вводятся нами в употребление, дабы не ограничивать число переменных, которые могут встретиться в произвольном выражении. Мы будем считать штрих( ' ) отдельным символом формальной системы, так что действительное количество символов в системе остается конечным. Помимо этого нам также потребуются символы для базовых арифметических операций =, +, х(«умножить») и т. д.; для различных видов скобок (, ), [, ], и для обозначения логических операций, таких как & (« и»), => (« следует»), V (« или»), <=> (« тогда и только тогда»), ~ (« не»). Дополнительно нам будут нужны еще и логические« кванторы»: квантор существования E _к.с. (« существует… такое, что») и квантор общности A _к.о. (« для любого… выполняется»). Тогда мы сможем такие утверждения, как, например, «последняя теорема Ферма», привести к виду:

— E _к.с. ω , х , у , z [( x + 1 ) ^ω+3 +

+ ( у + 1 ) ^ω+3 = ( z + 1 ) ^ω+3 ]

(см. главу 2, «Неразрешимость проблемы Гильберта»). (Я мог бы написать « 0111 » для « 3 », и, возможно, использовать для «возведения в степень» обозначение, более подходящее к рассматриваемому формализму; но, как уже говорилось, я буду придерживаться стандартной системы записи во избежании ненужной путаницы.) Это утверждение (если читать его до левой квадратной скобки) звучит как:

« Не существует таких натуральных чисел ω, х, у, z, что… ».

Мы можем также переписать последнюю теорему Ферма при помощи A _к.о.:

A _к.о. ω , х , у , z [~ ( х + 1 ) ^ω+3 + ( у + 1 ) ^ω+3 = ( z + 1 ) ^ω+3 ],

которое будет читаться следующим образом (заканчивая символом « не» после левой квадратной скобки):

« Для любых натуральных чисел ω, х, у, z не может быть выполнено… »,

что логически эквивалентно написанному ранее.

Нам понадобятся еще и буквы, обозначающие целые утверждения, для чего я буду использовать заглавные буквы Р , Q , R , S … Таким утверждением может, к примеру, служить и вышеприведенная теорема Ферма:

F = ~ E _к.с. ω , х , у , z [( x + 1 ) ^ω+3 + ( у + 1 ) ^ω+3 = ( z + 1 ) ^ω+3 ].

Утверждение может также зависеть от одной или более переменных; например, нас может интересовать формулировка теоремы Ферма для некоторого конкретного [71]значения степени ω + 3

G ( ω ) = ~ E _к.с. x , y , z [( x + 1 ) ^ω+3 + ( y + 1 ) ^ω+3 = ( z + 1 ) ^ω+3 ],

так что G ( 0 ) утверждает, что «куб не может быть суммой кубов положительных чисел»; G ( 1 ) говорит о том же применительно к четвертым степеням и так далее. (Обратите внимание на отсутствие ω после символа E _к.с. ). Тогда теорема Ферма гласит, что G ( ω ) выполняется для любого ω :

F = A _к.о. ω [ G ( ω )].

G () является примером так называемой функции исчисления высказываний, т. е. утверждением, которое зависит от одной или более переменных.

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

( P&Q ) => Р ,

— ( ~ Р ) <=> Р ,

— E _к.с. х [ R ( x )] <=>A _к.о. x [ ~ R ( x )],

«априорная истинность» которых уже заключена в их смысловых значениях. (Первое утверждение означает лишь, что «если выполняется Р и Q , то выполняется и Р »; второе устанавливает равносильность утверждений «неверно, что не выполняется Р » и « Р выполняется»; а третье может быть проиллюстрировано эквивалентностью двух способов формулировки теоремы Ферма, данных выше.) Мы можем также включить основные аксиомы арифметики:

A _к.о. х, у [ х + у = у + х ],

A _к.о. х , у , z [( x + у ) х z = ( x х z ) + ( у х z )],

хотя некоторые предпочитают определять арифметические операции через более простые понятия и выводить вышеуказанные утверждения как теоремы. Правила вывода могут вводиться в виде (самоочевидных) процедур типа

«Из Р и Р => Q следует Q ».

«Из A _к.о. x [ R ( x )] мы можем вывести любое утверждение, получающееся путем подстановки конкретного натурального числа x в R ( x )».

Такие правила являются инструкциями, следуя которым, можно с помощью утверждений, чья истинность уже доказана, получать новые утверждения.

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

Идея программы Гильберта состояла в том, чтобы найти применительно к любой отдельно взятой области математики набор аксиом и правил вывода, который был бы достаточно полным для всех возможных в данной области корректных математических рассуждений. Пусть такой областью будет арифметика (с добавленными кванторами E _к.с. и A _к.о. , позволяющими формулировать утверждения, подобные последней теореме Ферма). То, что мы не рассматриваем более общую область математики, не умаляет нашу задачу: арифметика и сама по себе обладает общностью, достаточной для применения процедуры Геделя. Если мы допустим, что благодаря программе Гильберта мы действительно располагаем такой всеобъемлющей системой аксиом и правил вывода для арифметики, то мы тем самым обретаем и определенный критерий для выявления «корректности» математического доказательства любого утверждения в области арифметики. Возлагались надежды на то, что подобная система аксиом и правил может быть полной в смысле предоставляемой нам принципиальной возможности решать, истинно или ложно произвольное утверждение, сформулированное в рамках этой системы.

Гильберт рассчитывал, что для любой строки символов, представляющих математическое утверждение, скажем, Р , можно будет доказать либо Р , либо ~ Р , если Р истинно или ложно, соответственно. Здесь мы в обязательном порядке оговариваем, что строка должна быть синтаксически корректна, где «синтаксически корректна» по сути означает «грамматически корректна» — то есть удовлетворяет всем правилам записи, принятым в данном формализме, среди которых будет правильное попарное соответствие скобок и т. п. — так чтобы Р всегда имело четко определенное значение «ложь» или «истина». Если бы надежды Гильберта оправдались, то можно было бы вообще не задумываться о том, что означает то или иное утверждение! Р было бы просто-напросто синтаксически корректной строкой символов. Строке было бы приписано значение ИСТИНА, если бы Р являлось теоремой (другими словами, если бы Р было доказуемо в рамках системы); или же ЛОЖЬ, если бы теоремой было ~ Р . Чтобы такой подход имел смысл, мы должны дополнительно к условию полноты наложить еще и условие непротиворечивости, гарантирующее отсутствие такой строки символов Р , для которой как Р , так и ~ Р были бы теоремами. Ведь в противном случае Р могло бы быть одновременно и ИСТИНОЙ, и ЛОЖЬЮ!

Такой подход, согласно которому можно пренебрегать смысловыми значениями математических выражений и рассматривать их лишь как строки символов некоторой формальной математической системы, в математике получил название формализма. Некоторым нравится эта точка зрения, с которой математика превращается в своего рода «бессмысленную игру». Однако я сам не являюсь сторонником таких идей. Все-таки именно «смысл» — а не слепые алгоритмические вычисления — составляет сущность математики. К счастью, Гедель нанес формализму сокрушающий удар! Давайте посмотрим, как он это сделал.

Теорема Геделя

Часть доказательства, приведенного Геделем, содержало некий очень сложный и детализированный кусок. Однако нам не обязательно разбираться во всех его тонкостях. Основная идея, в то же время, была проста, красива и глубока. И ее мы сможем оценить по достоинству. В «сложной» части (которая, впрочем, содержит много остроумных рассуждений) подробно показано, каким образом частные правила вывода и использование различных аксиом формальной процедуры могут быть представлены в виде арифметических операций. (Хотя в сложной части становится понятной плодотворность этих действий!) Для этого представления нам необходимо будет найти какой-нибудь удобный способ нумерации утверждений при помощи натуральных чисел. Один из способов мог бы заключаться в том, чтобы использовать своего рода «алфавитный» порядок для строчек символов формальной системы, имеющих одинаковую длину, упорядочить заранее строчки по длине. (Таким образом, за выстроенными в алфавитном порядке строками из одного символа будут следовать строки длиной в два символа, также упорядоченные по алфавиту; за ними идут строки из трех символов и так далее.) Это называется лексикографическим порядком [72]. В действительности Гедель использовал более сложную систему нумерации, но различия в данном случае для нас несущественны. Нас же должны в особенности интересовать функции исчисления высказываний одной переменной, наподобие введенной выше G ( ω ). Пусть n - я(из пронумерованных выбранным способом строк символов) такая функция от аргумента ω обозначается

P _n ( ω ).

Мы можем допустить, чтобы наша нумерация по желанию была несколько «либеральна» в отношении синтаксически некорректных выражений. (Это позволит значительно упростить перевод системы на язык арифметических операций по сравнению со случаем, когда мы будем стараться исключить из рассмотрения синтаксически некорректные выражения.) Если P _n (ω) синтаксически корректно, то оно будет представлять из себя некоторое совершенно определенное арифметическое выражение, в котором фигурируют два натуральных числа п и ад. Каков будет конкретный вид этого выражения — зависит от особенностей системы нумерации, которую мы выбрали. Но эти детали рассматриваются в «сложной» части и сейчас нас не касаются. Пусть П _n будет n -м доказательством. (Опять же мы можем использовать «либеральную нумерацию», когда для некоторых значений n выражение П _n не является синтаксически корректным и, тем самым, не доказывает никакую теорему.)

А теперь рассмотрим следующую функцию исчисления высказываний от натурального числа ω :

— E _к.с. x [ П _x доказывает P _ω ( ω )].

В выражении в квадратных скобках частично присутствуют слова, но, тем не менее, это — абсолютно точно определенное выражение. Оно говорит о том, что доказательство номер х является доказательством утверждения Р _ω (), примененного к самому ω . Находящийся за скобками квантор существования с отрицанием позволяет исключить из рассмотрения одну из переменных («не существует такого х , что…»), приводя нас в конечном счете к арифметической функции исчисления высказываний, зависящей только от ω . В целом данное выражение утверждает, что не существует доказательства Р _ω ( ω ). Я буду предполагать, что оно оформлено синтаксически корректным образом (даже если Р _n ( ω ) некорректно — поскольку тогда выражение было бы истинным за невозможностью существования доказательства синтаксически некорректного утверждения). На самом деле, в результате сделанного нами перевода на язык арифметики, написанное выше будет в действительности неким арифметическим выражением, включающим натуральное число ω (тогда как в квадратных скобках окажется четко определенное арифметическое выражение, связывающее два натуральных числа х и ω ). Конечно, возможность представления этого выражения в арифметическом виде далеко не очевидна, но она существует. Рассуждения, приводящие к этому заключению, составляют наиболее трудную задачу в «сложной» части доказательства Геделя. Как и ранее, непосредственный вид арифметического выражения будет зависеть от способа нумерации и в еще большей степени от конкретной структуры аксиом и правил вывода, принятых в нашей системе. Поскольку все это входит в «сложную» часть доказательства, то в данном случае нас не интересует.

Мы пронумеровали все функции исчисления высказываний, зависящие от одной переменной, поэтому той, которую мы ввели выше, также должен быть приписан номер. Пусть этот номер будет k . Наша функция будет в таком случае k -й в общем списке. То есть

— E _к.с. x [ П _х доказывает P _ω ( ω )] = Р _k ( ω ).

Теперь исследуем эту функцию при определенном значении: ω = k . Мы получаем:

E _к.с. х [ П _х доказывает P _k ( k )] = P _k ( k )

Данное утверждение P _k ( k ) является абсолютно точно определенным (синтаксически корректным) арифметическим выражением. Может ли оно быть доказано в рамках нашей формальной системы? А его отрицание ~ P _k ( k ) — имеет ли оно такое доказательство? Ответ в обоих случаях будет отрицательный. Мы можем убедиться в этом путем исследования смысла, который лежит в основании процедуры Геделя. Хотя P _k ( k ) является просто арифметическим выражением, последнее было построено нами таким образом, что написанное в левой части утверждает следующее: «внутри системы не существует доказательства P _k ( k )». Если мы были аккуратны в определении аксиом и процедур вывода, и не ошиблись при нумерации, то тогда в рамках системы такого доказательства найти невозможно. Если же доказательство существует, то значение утверждения, содержащегося в P _k ( k ) — о том, что такого доказательства нет, — будет ложным, а вместе с ним будет ложным и арифметическое выражение, отвечающее P _k ( k ). Но наша формальная система не может быть построена настолько плохо, чтобы включать в себя ложные утверждения, которые могут быть доказаны! Таким образом, в действительности, доказательство P _k ( k ) быть не может. Но это в точности то самое, о чем говорит нам P _k ( k ). То, что утверждает P _k ( k ), обязано, следовательно, быть верным, а поэтому P _k ( k ) должно быть верным как арифметическое выражение. Значит, мы нашли истинное утверждение, которое недоказуемо в рамках системы!

А как насчет ~ P _k ( k )? Из предыдущих рассуждений видно, что доказательство этому утверждению внутри системы мы найти не сможем. Мы только что установили, что ~ P _k ( k ) должно быть ложным (ибо P _k ( k ) является истинным), а мы, по определению, не имеем возможности доказывать ложные утверждения в рамках системы! Таким образом, ни P _k ( k ), ни ~ P _k ( k ) недоказуемы в нашей формальной системе, что и составляет теорему Геделя.

Математическая интуиция

Обратите внимание, что мы здесь сталкиваемся с одной примечательной особенностью. Часто думают, что теорема Геделя имеет, в некотором роде, отрицательный смысл, поскольку она указывает на принципиальные ограничения в применении формальных математических рассуждений. Независимо от нашего мнения об универсальности применяемого подхода, всегда найдутся утверждения, которые не попадают в сферу его действия. Но насколько, в действительности, нас могут затрагивать частные случаи типа P _k ( k )? В ходе предыдущих рассуждений мы установили, что P _k ( k ) — истинное утверждение! Мы смогли это сделать несмотря на то, что это утверждение формально недоказуемо в рамках системы. А вот математических формалистов это должно волновать, потому что наши рассуждения с необходимостью приводят к выводам о неполноте их понятия «истины». Какая бы (непротиворечивая) формальная система не использовалась для арифметики, в ней будут содержаться утверждения, понимаемые нами как истинные, но которым не может быть приписано значение ИСТИНА при помощи вышеописанной формальной процедуры. Способ, при помощи которого формалист сумел бы обойти подобные трудности, мог бы состоять в том, чтобы не говорить о понятии истины, а только лишь о доказуемости внутри конкретной формальной системы. Однако же, такой подход весьма ограничен. Он не позволил бы даже сформулировать утверждение Геделя и осуществить его доказательство, как это было сделано выше, поскольку в значительной части рассуждений речь идет как раз об определении того, что есть ложь, а что — истина [73]. Некоторые формалисты встают на более «прагматическую» точку зрения, заявляя, что их не волнуют утверждения, подобные P _k ( k ), поскольку они исключительно сложны и не интересны в качестве арифметических выражений. Отстаивают они свою точку зрения примерно так:

Несомненно, что утверждения вида P _k ( k ), будучи полностью выписанными, были бы чрезвычайно громоздки и выглядели бы странно для числовых математических выражений. Однако за последнее время были выдвинуты сравнительно простые выражения приемлемого с точки зрения математики характера, которые эквивалентны утверждениям Геделя [74]. Они недоказуемы на основании обычных аксиом арифметики, однако же следуют из некоего свойства «самоочевидности», которым обладает сама система аксиом.

Отсутствие интереса к «математической истине», исповедуемое формалистами, кажется мне очень странной позицией в приложении к философии математики. Более того: она совсем не так прагматична, как представляется. Когда математики проводят свои выкладки, они не намерены постоянно проверять, могут ли они быть сформулированы посредством аксиом и правил вывода некоторой сложной формальной системы. Единственно, что необходимо — быть уверенным в правомерности использования этих рассуждений для установления истины. Доказательство Геделя удовлетворяет этому требованию, так что P _k ( k ) является математической истиной с таким же правом, как и любое другое утверждение, полученное более стандартным путем с использованием изначально заданных аксиом и правил вывода.

Процедура, которая напрашивается сама собой, заключается в следующем. Давайте положим, что P _k ( k ) — совершенно верное утверждение (переобозначим его здесь как G ₀ ). Тогда мы можем присоединить его к нашей системе в качестве дополнительной аксиомы. Естественно, что наша новая система будет, в свою очередь, содержать новое утверждение Геделя, скажем, G ₁ , которое также будет истинным числовым выражением. Соответственно, мы можем и G ₁ добавить в нашу систему. Это даст нам новую улучшенную систему, которая также содержит новое утверждение Геделя G ₂ (опять же совершенно справедливое); и мы сможем снова добавить его к системе, получая следующее утверждение Геделя G ₃ , которое мы тоже присоединяем — и так далее, повторяя этот процесс неограниченно. Что мы можем сказать о получившейся в результате системе, где мы используем весь набор G ₀, G ₁, G ₂, G ₃…. как дополнительные аксиомы? Может ли эта система быть полной? Поскольку мы теперь имеем неограниченную (бесконечную) систему аксиом, то возможность применения процедуры Геделя совсем не очевидна. Однако, это последовательное включение утверждений Геделя является в высшей степени систематичной схемой, результат применения которой может быть истолкован как обычная конечная система аксиом и правил вывода. Эта система будет иметь свое собственное утверждение Геделя G _ω которое мы также сможем к ней присоединить, получая новую систему и с ней — еще одно утверждение Геделя G _ω+1 . Продолжая, как и ранее, мы получаем набор утверждений G _ω , G _ω+1 , G _ω+2 , G _ω+3 , каждое из которых истинно и может быть включено в нашу формальную систему. Сохраняя свойство строгой систематичности, этот процесс вновь приводит нас к созданию новой системы, которая охватывает все созданные к этому моменту аксиомы. Но и эта система, в свою очередь, имеет свое собственное утверждение Геделя, скажем, G _ω+ω — которое можно переписать как G _ω2 , и мы можем начать всю процедуру заново. В результате этого мы получим новый бесконечный, но систематический, набор аксиом G _ω2 , G _ω2+1 , G _ω2+2 , и т. д., приводящий к еще одной новой системе — и новому утверждению Геделя G _ω3 . Воспроизводя весь процесс, мы получаем G _ω4 , потом — G _ω5 и так далее. И эта схема также будет полностью систематичной и даст свое собственное утверждение Геделя G _{ω ²} .

Есть ли логическое завершение у этого процесса? В определенном смысле — нет; но это приводит нас к ряду трудных математических рассуждений, которые здесь не могут быть нами рассмотрены во всех деталях. Вышеуказанная процедура обсуждалась Аланом Тьюрингом в статье [75], опубликованной в 1939 году. Примечательно, что на самом деле любое истинное(в общепринятом смысле) утверждение в арифметике может быть получено путем повторения процедуры «геделизации» такого рода (см. Феферман [1988]). Однако это может вызвать вопрос о том, как мы в действительности решаем, является ли утверждение истинным или ложным. Исключительно важным будет также понять, как на каждом этапе нужно выполнять присоединение бесконечного семейства утверждений Геделя, чтобы они порождали единственную дополнительную аксиому (или конечное число аксиом). Для выполнения такого присоединения требуется определенная алгоритмическая систематизация нашего бесконечного семейства. Чтобы быть уверенным в том, что подобная систематизация корректна и приводит к желаемому результату, нам придется опереться на интуитивные представления, выходящие за рамки системы — точь-в-точь, как мы это сделали для установления истинности P _k ( k ). Именно эти «прозрения» и не могут быть систематизированы, не говоря о том, что они должны лежать вне сферы действия любой алгоритмической процедуры!

Интуитивная догадка, которая позволила нам установить, что утверждение Геделя P _k ( k ) является на самом деле истинным, представляет собой разновидность общей процедуры, известной логикам как принцип рефлексии: посредством нее, размышляя над смыслом системы аксиом и правил вывода и убеждаясь в их способности приводить к математическим истинам, можно преобразовывать интуитивные представления в новые математические выражения, невыводимые из тех самых аксиом и правил вывода. То, как нами была выше установлена истинность P _k ( k ), как раз базировалось на применении этого принципа. Другой принцип рефлексии, имеющий отношение к доказательству Геделя (хотя и не упомянутый выше), опирается на вывод новых математических истин исходя из представления о том, что система аксиом, которую мы полагаем априори адекватной для получения математических истин, является непротиворечивой. Применение принципов рефлексии часто подразумевает размышления о бесконечных множествах, и при этом нужно быть всегда внимательным и остерегаться рассуждений, которые могут привести к парадоксам наподобие расселовского. Принципы рефлексии полностью противопоставляются рассуждениям формалистов. Если использовать их аккуратно, то они позволяют вырваться за жесткие рамки любой формальной системы и получить новые, основанные на интуитивных догадках, представления, которые ранее казались недостижимыми. В математической литературе могло бы быть множество приемлемых результатов, чье доказательство требует «прозрений», далеко выходящих за рамки исходных правил и аксиом стандартной формальной системы арифметики. Все это свидетельствует о том, что деятельность ума, приводящая математиков к суждениям об истине, не опирается непосредственно на некоторую определенную формальную систему. Мы убедились в истинности утверждения Геделя P _k ( k ), хотя мы и не можем вывести ее из аксиом системы. Этот тип «вйдения», используемый в принципе рефлексии, требует математической интуиции, которая не является результатом чисто алгоритмических операций, представимых в виде некоторой формальной математической системы. Мы вернемся к этому вопросу в главе 10.

Читатель может заметить определенное сходство между рассуждениями, устанавливающими, вопреки «недоказуемости», истинность P _k ( k ), и парадоксом Рассела. Помимо этого, наблюдается сходство и с доказательством Тьюринга о невозможности существования «машины Тьюринга», которая могла бы решить проблему остановки. Эти сходства не случайны. Между этими тремя событиями имеется прочная историческая нить. Тьюринг пришел к своему доказательству после изучения работ Геделя. Сам Гедель был очень близко знаком с парадоксом Рассела и смог преобразовать те парадоксальные рассуждения, которые уводили слишком далеко в область логических абстракций, в состоятельное математическое доказательство. (Все эти утверждения уходят корнями к диагональному процессу Кантора, описанному в предыдущей главе)

Почему мы должны принимать доказательства Геделя и Тьюринга и в то же время сбрасывать со счетов рассуждения, ведущие к парадоксу Рассела? Первые являются более ясными и безупречными с точки зрения математики, тогда как парадокс Рассела строится на более туманных рассуждениях об «огромных» множествах. Но нужно признать, что различия здесь не настолько очевидны, как нам хотелось бы. Попытка придать этим различиям ясность была лейтмотивом всей идеи формализма. Доказательство Геделя, с одной стороны, показывает, что строгий формальный подход не выдерживает критики, но с другой стороны, оно не приводит нас к абсолютно надежной альтернативе. По-моему, этот вопрос до сих пор не разрешен. Процедура, используемая в современной математике с целью избежать рассуждений, вовлекающих в рассмотрение «огромные» множества и приводящих к парадоксу Рассела, не является полностью удовлетворительной [76]. Более того, она, как правило, формулируется в чисто формалистских терминах — или же в терминах, которые не дают нам полной уверенности, что в результате их использования не возникнет противоречий.

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

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

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

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

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

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

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

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

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

3,14152653589793….

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

π = 3,14152653…

…77777777777777777777…,

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

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

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

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

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

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

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

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

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

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

В действительности теорема Геделя носит более частный характер, поскольку от формальной системы того типа, который рассматривал Гедель, требовалась адекватность по отношению к арифметическим утверждениям, а не математическим утверждениям вообще. Можем ли мы устроить так, чтобы все необходимые операции машины Тьюринга выполнялись только при помощи арифметики? Или, иными словами, могут ли все вычислимые функции натуральных чисел (т. е. рекурсивные, или алгоритмические функции — результаты действия машины Тьюринга) быть выражены в терминах обычной арифметики? На самом деле это так, хотя и не совсем. Нам понадобится одна дополнительная операция, которую мы добавим в систему стандартных правил арифметики и логики (включая кванторы 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… }, равно как и пустое множество ø = {}. Нас будут интересовать только вопросы вычислимости, скажем: «Какие множества натуральных чисел могут быть сгенерированы с помощью алгоритма, а какие — нет?»

Чтобы сформулировать такой вопрос, мы можем считать, что каждое отдельное число 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].

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

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

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

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

Существуют некоторые простые классы истинных арифметических утверждений, которые все же образуют рекурсивно нумеруемые множества. Например, как это нетрудно видеть, истинные утверждения вида

E _к.с. ω , x …, z [ f ( ω , x ,…, z ) = 0 ],

где f () — некоторая функция, построенная из обычных арифметических операций сложения, вычитания, умножения и возведения в степень, составляют рекурсивно нумеруемые множества [83](которые я обозначу через А ). Пример утверждения такого рода — хотя мы не знаем, верно ли оно — это отрицание последней теоремы Ферма [84]., для которой мы можем взять за f () функцию

f ( ω , х , у , z ) = ( х + 1 ) ^{ω + 3} + ( у + 1 ) ^{ω + 3} - ( z + 1 ) ^{ω + 3} .

Однако, множество А не является рекурсивным (факт, который не так легко установить, хотя он и вытекает из оригинального доказательства Геделя). Значит, мы не имеем никаких алгоритмических средств для выяснения — хотя бы в принципе — истинности или ложности последней теоремы Ферма.

На рис. 4.1 я попытался схематически представить рекурсивное множество как фигуру с простой и изящной границей, так что кажется, что определить непосредственно принадлежность произвольной точки этому множеству — дело несложное. Каждая точка на рисунке соответствует некоторому натуральному числу. При этом дополнительное множество также представлено в виде просто выглядящей области на плоскости. На рис. 4.2 я постарался изобразить рекурсивно нумеруемое, но не рекурсивное множество в виде области со сложной границей, где подразумевается, что множество с одной стороны границы, — той, что рекурсивно нумеруема — должно выглядеть проще, чем с другой.

Фигуры очень схематичны и не претендуют на какую бы то ни было «геометрическую аккуратность». И конечно же, не стоит придавать большого значения тому, что эти рисунки изображены так, как если бы они были расположены на двумерной плоскости!

На рис. 4.3 я схематично обозначил, как расположены области Р , Т и А внутри множества N .

Является ли множество Мандельброта рекурсивным?

Существенной характеристикой нерекурсивных множеств является их сложноорганизованность. Это свойство должно, в некотором смысле, препятствовать любым попыткам систематизации, которая, в противном случае, привела бы к некоторой «работающей» алгоритмической процедуре. Для нерекурсивного множества не существует общего алгоритмического пути к решению вопроса о принадлежности ему произвольного элемента (или «точки»), В начале третьей главы мы встретились с неким чрезвычайно сложно выглядящим множеством — с множеством Мандельброта. Хотя правила, по которым оно строится, поразительно просты, само множество представляет собой бесконечное разнообразие в высшей степени замысловатых структур. Может ли это быть примером настоящего нерекурсивного множества, явленного глазам смертных?

Читателю, однако, не понадобится много времени, чтобы сообразить, что эта парадигма сложности была создана специально для наших глаз волшебством вычислительных технологий с использованием современных быстродействующих компьютеров. А не являются ли компьютеры истинным воплощением алгоритмических действий? Конечно, это так, но все же мы должны принимать во внимание способ, с помощью которого компьютеры, в действительности, создают эти картинки. Чтобы проверить, принадлежит точка плоскости Аргана — комплексное число с — множеству Мандельброта (закрашено черным) или его дополнению (светлая область), компьютер, начиная с нуля, применит отображение

z → z ² + с

сначала к z = 0 , чтобы получить с ; потом к z = с , чтобы получить с ² + с ; затем к z = с ² + с , чтобы получить с ⁴ + 2с ³ + с ² + с ; и так далее. Если эта последовательность 0 , с , с ² + с , с ⁴ + 2с ³ + с ² + с … остается ограниченной, то соответствующая точка с будет черной; в противном случае — белой. Как машина определяет, что такая последовательность остается ограниченной? В принципе, этот вопрос предполагает наличие информации о том, что происходит после бесконечного числа ее элементов! Сама по себе эта задача вычислительными методами не решается. К счастью, существуют способы предсказать исходя уже из конечного числа членов, когда последовательность станет неограниченной. (На самом деле, если последовательность достигает окружности радиуса 1 + √2 с центром в начале координат, можно с уверенностью сказать, что она будет неограниченной.)

Таким образом, дополнение к множеству Мандельброта является, в некотором смысле, рекурсивно нумеруемым. Если комплексное число с расположено в светлой области, то существует алгоритм, подтверждающий этот факт. А как насчет самого множества Мандельброта — темного участка рисунка? Существует ли алгоритм, способный точно установить, что точка, принадлежащая предположительно темному участку, действительно ему принадлежит? Ответ на этот вопрос в настоящее время, похоже, отсутствует [85]. Я справлялся у многих коллег и экспертов, но ни один из них не слышал о подобном алгоритме. Равно как и никто из них не сталкивался с указанием на то, что такого алгоритма не существует. По крайней мере, насколько можно об этом судить, алгоритм для темной области на сегодняшний день неизвестен. Возможно, множество, дополнительное по отношению к множеству Мандельброта, действительно является примером рекурсивно нумеруемого, но не рекурсивного множества!

Прежде чем исследовать дальше это предположение, необходимо будет обсудить некоторые моменты, которые я ранее опускал. Эти вопросы будут довольно важны для нас в дальнейших рассуждениях по поводу вычислимости в физике. Я хотел бы заметить, что, на самом деле, я был несколько неточен в предшествующем изложении. Я применял такие понятия, как «рекурсивно нумеруемый» и «рекурсивный», к множествам точек в плоскости Аргана, т. е. множествам комплексных чисел. Но эти термины могут применяться только лишь для натуральных чисел и других счетных множеств. Мы видели в третьей главе («Сколько же всего действительных чисел»), что действительные числа не могут быть счетным множеством, равно как, следовательно, и комплексные — ведь любое действительное число может быть рассмотрено как частный случай некоторого комплексного числа с нулевой мнимой частью (гл.3 «Комплексные числа»). В действительности существует такое же «количество» комплексных чисел, как и действительных, а именно « С». (Чтобы установить взаимнооднозначное соответствие между комплексными и действительными числами, можно, грубо говоря, просто взять действительную и мнимую части комплексного числа (записанные в десятичной форме) и перемешать через одну поразрядно цифры из мнимой части с цифрами из вещественной, образуя, тем самым, действительное число: тогда, например, 3,6781…+ i512,975… будет соответствовать действительному числу 50 132,6977851…)

Дабы избежать этой проблемы, можно было бы ограничиться только вычислимыми комплексными числами, так как мы еще в третьей главе видели, что вычислимые действительные числа — а значит, и соответствующие им комплексные — являются счетными. Однако здесь кроется одна принципиальная трудность: не существует алгоритма, с помощью которого можно было бы сравнивать два вычислимых числа, полученных алгоритмически! (Мы можем алгоритмическим образом составить их разность, но мы не в состоянии будем выяснить, равна она нулю или нет. Представьте себе два алгоритма, которые генерируют цифры 0,99999… и 1,00000…, соответственно; мы никогда не узнаем, продолжаются ли нули и девятки в них до бесконечности — так, что числа оказываются равными — или же где-то в дробной части того или другого числа могут появиться иные цифры, делая эти числа неравными.) Таким образом, мы, возможно, никогда не сможем определить, равны ли между собой такие числа. Как следствие этого — наша неспособность решить даже в таком простом случае как единичный круг в плоскости Аргана (множество точек, лежащих на расстоянии не большем единицы от начала координат — черная фигура на рис. 4.4), лежит ли комплексное число в этом круге или нет.

Трудность возникает не с точками, лежащими внутри или снаружи, а именно с точками на самой границе круга — то есть на самой единичной окружности. Эта окружность рассматривается по условию как часть круга. Предположим, что нам уже предоставлен в распоряжение алгоритм для получения цифр вещественной и мнимой частей некоторого комплексного числа. Если мы предполагаем, что это комплексное число лежит на единичной окружности, то мы не можем с необходимостью подтвердить этот факт. Не существует алгоритма, чтобы установить, является ли вычислимое число x ² + y ² равным единице, что служит критерием для принадлежности комплексного числа х + iy данной единичной окружности.

Очевидно, это совсем не то, что нам нужно. Единичный круг, безусловно, должен рассматриваться как рекурсивное множество. Едва ли найдется сколь-нибудь значительное число множеств, более простых, чем единичный круг! Чтобы обойти эту проблему, одним из способов может быть игнорирование границы. Ведь для точек, лежащих внутри (или снаружи), безусловно существует алгоритм, устанавливающий этот факт. (Можно просто последовательно генерировать цифры числа х ² + у ² , и, в конце концов, мы найдем цифру, отличную от 9 в дробной части 0,9999… или отличную от 0 — в дробной части 1,00000…) В этом смысле единичный круг является рекурсивным. Но этот подход чрезвычайно неудобен для математики, поскольку там часто возникает необходимость ссылаться в рассуждениях на то, что происходит именно на границах. С другой стороны, вполне возможно, что такая точка зрения окажется применимой в области физики. Позднее нам еще придется вернуться к этому вопросу.

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

Для меня совершенно не очевидно, что какой-либо из этих методов дает то, что нам нужно [86]. Философия «игнорирования границ», будучи приложенной к множеству Мандельброта, может привести к потере большого числа тонких моментов. Одна часть этого множества состоит из «клякс» — внутренних областей, а другая — из «усиков». Наибольшие сложности при этом связаны, видимо, с «усиками», которые могут «извиваться» самым причудливым образом. Однако, «усики» не принадлежат внутренней части множества, и, тем самым, они были бы проигнорированы, используй мы любой из двух вышеприведенных подходов. Но даже при таком допущении остается неясность, можно ли считать множество Мандельброта рекурсивным в том случае, когда рассматриваются только «кляксы». Похоже, что вопрос этот связан с некоторым недоказанным предположением, касающимся самого множества, а именно: является ли оно, что называется, «локально связным»? Я не собираюсь здесь разбирать значение этого понятия или его важность для данного вопроса. Я хочу просто показать, что существует ряд трудностей, которые вызывают неразрешенные на сегодняшний день вопросы, касающиеся множества Мандельброта, чье решение — первоочередная задача для некоторых современных математических исследований.

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

129z ⁷ — ЗЗz ⁵ + 725z ⁴ + 16z ³ — 2z — 3 = 0

— это алгебраические числа. Такие числа будут счетными и вычислимыми, и задача проверки двух из них на равенство будет решатся путем прямого вычисления. (Как выясняется, многие из них будут лежать на границе единичного круга и «усиков» множества Мандельброта.) И мы можем по желанию рассматривать вопрос о рекурсивности множества Мандельброта в терминах этих чисел.

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

y ≥ e ^z ,

где х + iy (= z ) — точка в плоскости Аргана.

Внутренняя часть множества, равно как и внутренняя часть его дополнения, будут рекурсивно нумеруемыми в соответствии с любой из вышеизложенных точек зрения, но (как следует из знаменитой теоремы Ф.Линдеманна, доказанной в 1882 году) граница, у = е ^х , содержит только одну алгебраическую точку, а именно точку z = i . В этом случае алгебраические числа никак не могут нам помочь при исследовании алгоритмической по своей природе границы!

Несложно определить другой подкласс вычислимых чисел, которые будут подходить в данном конкретном случае, но при этом все равно останется ощущение, что правильный подход нами до сих пор так и не был найден.

Некоторые примеры нерекурсивной математики

Существует немало областей математики, где возникают проблемы нерекурсивного характера. Это означает, что мы можем сталкиваться с задачами, ответ к которым в каждом случае либо «да», либо «нет», но определить, какой из них верен, — нельзя из-за отсутствия соответствующего общего алгоритма. Некоторые из этих классов задач выглядят на удивление просто.

Например, рассмотрим задачу об отыскании целочисленных решений системы алгебраических уравнений с целыми коэффициентами. Эти уравнения известны под именем диофантовых(в честь греческого математика Диофанта, который жил в третьем веке до нашей эры и изучал уравнения такого типа). Подобные уравнения выглядят, например, как

z ³ - y — 1= 0,

yz ²— 2x— 2 = 0,

у ²— 2xz + z + 2 = 0,

и задача состоит в том, чтобы определить, могут ли они быть решены в целых x , y , z . Оказывается, что в этом конкретном случае существует тройка целых чисел, дающая решение этой системы:

х = 13, у = 7, 2 = 2.

Но для произвольной системы диофантовых уравнений никакого алгоритма не существует [87]. Арифметика Диофанта, несмотря на простоту входящих в нее выражений, является частью неалгоритмической математики!

(Несколько менее тривиальным является пример топологической эквивалентности многообразий. Я упоминаю об этом только вкратце, ибо в главе 8 будут рассматриваться вопросы, имеющие к данному определенное отношение. Чтобы понять, что такое «многообразие», представьте для начала петлю, которая является многообразием в одном измерении; затем представьте замкнутую поверхность — многообразие в двух измерениях. Далее попробуйте представить некую «поверхность», имеющую три и более измерений. «Топологическая эквивалентность» двух многообразий означает, что одно из них может быть деформировано в другое путем непрерывных преобразований — без разрывов и склеек. Так, сфера и поверхность куба являются топологически эквивалентными, хотя они не эквивалентны поверхности кольца или чашки с ручкой — хотя последние топологически эквивалентны друг другу. При этом для двумерных многообразий существует алгоритм, позволяющий определить, эквивалентны ли произвольные два многообразия друг другу или нет — в сущности, заключающийся в подсчете «ручек», которые имеет каждая из поверхностей. Для случая трех измерений вопрос о существовании такого алгоритма на момент написания книги остается без ответа; однако для четырех и более измерений уже известно, что такого алгоритма быть не может . Возможно, четырехмерный случай имеет некое отношение к физике, поскольку согласно теории общей относительности Эйнштейна пространство и время совместно образуют четырехмерное многообразие (см. главу 5, «Специальная теория относительности Эйнштейна и Пуанкаре»). Герох и Хартли в 1986 году высказали предположение о том, что свойство неалгоритмичности может иметь отношение к «квантовой гравитации» (см. также главу 8).)

Давайте теперь рассмотрим иной тип задач, называемых задачами со словами [88]. Допустим, у нас есть некий алфавит символов, и мы рассматриваем различные строки этих символов, трактуя их как слова . Слова могут сами по себе не иметь никакого значения, но мы должны иметь некоторый (конечный) список «равенств» между ними, которые мы сможем использовать для дальнейшего построения таких «равенств». Это делается путем подстановки слов из исходного списка в другие (как правило, более длинные) слова, которые содержат их в виде составных частей. Каждая такая часть может быть заменена на равную ей в соответствии с используемым списком. Тогда для любой данной пары слов мы должны решить задачу об их равенстве согласно этим правилам.

В качестве примера мы можем взять для нашего исходного списка, скажем, такие равенства:

EAT = АТ

АТЕ = А

LATER = LOW

PAN = PILLOW

CARP = ME.

Отсюда мы можем, например, вывести

LAP = LEAP,

используя последовательные замены из второго, первого и снова второго соотношения из нашего исходного листа:

LAP = LATEP = LEATEP = LEAP.

Проблема теперь заключается в том, чтобы выяснить, сможем ли мы для любой наперед заданной пары слов осуществить вышеописанным образом переход от одного из них к другому? Можем мы перейти от CATERPILLAR к MAN, или, скажем, от CARPET — к MEAT? Ответ в первом случае оказывается утвердительным, тогда как во втором — отрицательным. Когда ответ утвердителен, стандартный путь показать его справедливость заключается в построении цепочки равенств, где каждое из слов получается из предыдущего с учетом допустимых соотношений. Итак, имеем (обозначая буквы, назначенные к замене, жирным шрифтом, а только что измененные — курсивом):

Как мы можем утверждать, что посредством разрешенных подстановок невозможно получить MEAT из CARPET? Для демонстрации этого факта придется подумать чуть больше, однако показать это не так уж сложно, причем множеством разных способов. Простейшим представляется следующий: в каждом «равенстве» из нашего списка число букв А плюс число букв W плюс число букв М с каждой стороны одинаково. Значит, общая сумма указанных букв не может меняться в процессе преобразования по допустимым нашим списком правилам. Однако, для CARPET эта сумма равна 1 , а для MEAT— 2 . Следовательно, не существует способа получить из первого слова второе при помощи вышеприведенного списка равенств.

Заметьте, что когда два слова «равны», мы можем показать это, просто приведя допустимую формальную строчку символов, построенную с помощью заданных нами правил; тогда как в случае их «неравенства» мы должны прибегать к рассуждениям об этих самых правилах. Существует четкий алгоритм, который мы можем использовать для установления «равенства» между двумя словами в том случае, когда они действительно «равны». Все, что нам требуется, это составить лексикографический перечень всех возможных последовательностей слов, и потом вычеркнуть из этого списка любую строчку, где имеется пара слов, в которой последующее нельзя получить из предыдущего при помощи какого бы то ни было правила из исходного списка. Оставшиеся последовательности дадут нам набор всех искомых «равенств» между словами. Однако, в общем случае нет такого явного алгоритма для случая, когда два слова «неравны», и нам, возможно, пришлось бы применить «интеллект» для установления этого факта. (Конечно же, мне потребовалось некоторое время, прежде чем я заметил описанный выше «трюк», при помощи которого доказал, что CARPET и MEAT«неравны». А для другого примера «трюк» мог бы понадобиться совершенно иной. Кстати, интеллект помогает — хотя и не обязательно — и в случае, когда необходимо установить существование некоторого «равенства».)

В действительности, для нашего конкретного списка из пяти «равенств», которые составляют исходный список в рассмотренном выше примере, привести алгоритм, устанавливающий «неравенство» в случае, когда два слова и вправду «неравны» — не так уж сложно. Однако, чтобы отыскать алгоритм в этом случае, потребовалась изрядная работа интеллекта! И, конечно, оказывается, что не существует единого универсального алгоритма для всех возможных вариантов исходного списка. Общая задача со словами принадлежит области нерекурсивной математики!

Существуют даже определенные варианты выбора исходного списка, для которых нет алгоритма решения задачи сравнения двух слов. Один из них дается таким набором:

АН = НА

ОН = НО

АТ = ТА

ОТ = ТО

TAI = IT

HOI = IH

THAT = ITHT.

(Этот список взят из списка, предложенного Григорием Цейтиным и Даной Скотт в 1955 году (см. Гарднер [1958]).) Таким образом, эта частная задача со словами служит примером нерекурсивной математики в том смысле, что, используя такой исходный список, мы не можем алгоритмическим путем решить, «равны» два наперед заданных слова или нет.

Общая задача со словами возникает как следствие рассмотрения формализованной математической логики («формальных систем» и т. п., в соответствии с обсуждаемым ранее). Исходный список выполняет роль системы аксиом, а правила замены слов — правил вывода. Доказательство нерекурсивности задачи со словами вытекает из подобных рассуждений.

В качестве последнего примера задачи из области нерекурсивной математики давайте рассмотрим вопрос о покрытии Евклидовой плоскости многоугольниками, разнообразие форм которых ограничено, а сам вопрос при этом ставится так: можем ли мы выложить всю плоскость полностью, без разрывов и нахлестов, используя фигуры только данных нам форм? Такая укладка фигур называется замощением плоскости. Мы знаем, что такое замощение возможно при помощи только квадратов, только равнобедренных треугольников или только правильными шестиугольниками (как изображено на рис. 10.2 гл. 10 «Плиточные» структуры и квазикристалы»), но невозможно, если использовать только правильные пятиугольники. Многими иными фигурами, такими, как два неправильных пятиугольника на рис. 4.6, также можно выложить плоскость.

Замощение фигурами двух форм может стать более хитроумной задачей. Два простых примера даны на рис. 4.7.

Все эти замощения являются периодическими; это означает, что они в точности повторяются по всей плоскости в двух независимых направлениях. На языке математики мы бы сказали, что существует параллелограмм периодов— параллелограмм, который, будучи неким образом выделен и затем повторен снова и снова в двух направлениях, параллельных его сторонам, даст в результате заданный узор покрытия. На рис. 4.8. представлен пример, где периодическое покрытие слева состоит из «плиток» в форме шипов, а справа указан соответствующий параллелограмм периодов.

С другой стороны, существует множество типов замощений плоскости, которые не являются периодическими.

Рис. 4.9 изображает три непериодических «спиральных» замощения из таких же шиповидных «плиток», как и на рис. 4.8.

Эта форма «плиток», известная как «универсальная» (по вполне понятным причинам!), была предложена Б. Грюнбаумом и Дж. К. Шепардом [1981, 1987] на основании форм, изученных X. Фодербергом. Обратите внимание, что универсальная форма позволяет замостить плоскость как периодически, так и непериодически. Это свойство характерно и для многих других форм единичных «плиток» и наборов «плиток». А могут ли существовать «плитки» (или конечные наборы «плиток»), которые бы покрывали плоскость только непериодически? Ответ на этот вопрос будет «да». На рис. 4.10 я изобразил сконструированный американским математиком Рафаэлем Робинсоном набор из фигур шести различных форм, которым можно замостить всю плоскость, но только непериодическим образом.

Небесполезно было бы сделать историческое отступление и посмотреть, как появился это непериодический набор (см. Грюнбаум, Шепард [1987]). В 1961 году американский логик китайского происхождения Хао Ванг поставил вопрос о существовании процедуры для решения задачи замощения, или, иными словами, о нахождении алгоритма, который позволил бы выяснить возможность замощения всей плоскости с помощью конечного набора многоугольников различной формы! [89]Ему удалось показать, что такая процедура могла бы существовать, если бы получилось доказать следующую гипотезу: любой конечный набор разных «плиток», с помощью которого можно каким-нибудь способом выполнить замощение плоскости, пригоден также и для ее периодического замощения. Мне думается, в то время интуитивно казалось, что не может существовать набор «плиток», нарушающий это условие (т. е. не может существовать «непериодический» набор плиток). Однако в 1966 году, следуя в указанном Хао Вангом направлении, Роберт Бергер смог показать, что, на самом деле, процедуры решения задачи покрытия не существует: эта задача также принадлежит области нерекурсивной математики! [90]

С учетом доказанного Хао Вангом это означало, что хотя бы один непериодический набор «плиток» должен существовать; и Бергер смог построить первый такой набор. Однако, из-за сложности выбранного им способа рассуждений, его набор состоял из ненормально большого числа «плиток» разной формы — изначально их насчитывалось 20 426. Использовав некоторый дополнительный искусный прием, Бергеру удалось сократить это число до 104. А в 1971 году Рафаэль Робинсон довел его до шести, которые изображены на рис. 4.10 выше.

Другой непериодический набор из шести «плиток» представлен на рис. 4.11. Это множество я придумал сам в 1973 году, следуя в своих рассуждениях несколько отличным путем. (Я вернусь к этой теме в главе 10 «Плиточные структуры и квазикристаллы», где на рис. 10.3, изображен массив, покрытый такими «плитками».)

После того, как, я познакомился с «шестиплиточным» набором Робинсона, я начал думать о том, как сократить их число; и путем различных манипуляций с разрезаниями и склеиванием я, в конечном счете, смог довести количество «плиток» до двух. Две альтернативные схемы представлены на рис. 4.12.

Узоры, которые получаются в результате полного замощения и имеющие с необходимостью непериодическую структуру, обладают рядом замечательных свойств, в том числе — кажущейся невозможной с точки зрения кристаллографии квазипериодической симметрией с осью пятого порядка. К этому вопросу я вернусь позднее.

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

Задача замощения, в том виде, как она исследовалась Вангом, Бергером и Робинсоном, формулируется для «плиток», построенных на квадратах. Я же здесь допускаю рассмотрение многоугольников произвольной формы, и поэтому необходимо наличие какого-нибудь способа изображения каждой из «плиток», поддающегося адекватному вычислению. Одним из таких путей могло бы быть представление вершин «плиток» точками плоскости Аргана, которые превосходно задаются алгебраическими числами.

Похоже ли множество Мандельброта на нерекурсивную математику?

Давайте теперь вернемся к нашей предшествующей дискуссии о множестве Мандельброта. Я буду для наглядности предполагать, что это множество является в некотором смысле нерекурсивным. Поскольку его дополнение рекурсивно нумеруемо, то, как следствие, само оно таковым быть не может. Я думаю, что форма множества Мандельброта может кое-чему научить нас о том, что касается природы нерекурсивных множеств и нерекурсивной математики.

Посмотрим еще раз на рис. 3.2, с которым мы встретились в третьей главе («страна Тор'Блед-Нам»). Заметьте, что большая часть множества вписывается в сердцевидную фигуру, которую я обозначил на рис. 4.13 через А(ниже). Эта фигура называется кардиоида и ее внутренняя область может быть определена математически как множество точек с плоскости Аргана, которые удовлетворяют равенству

с = z - z ² ,

где z — комплексное число, чье расстояние до центра координат меньше 1/2 . Это множество является, с очевидностью, рекурсивно нумеруемым в смысле существования алгоритма, который для произвольной точки внутренней области фигуры умеет подтверждать ее принадлежность этой самой области. Этот алгоритм легко получается из указанной выше формулы.

Теперь рассмотрим дисковидную фигуру слева от основной кардиоиды (область В на рис. 4.13).

Ее внутренняя часть представляет собой множество точек

с = z — 1 ,

где z — удалено от начала координат на расстояние меньше 1/4. Эта область, несомненно, является внутренностью диска, так как представляет собой множество точек, лежащих внутри правильной окружности. И, опять же, эта область является рекурсивно нумеруемой в принятом нами смысле. А как насчет других «бородавок» на кардиоиде? Возьмем две следующие по величине «бородавки». Это практически круглые «кляксы», располагающиеся примерно наверху и внизу кардиоиды на рис. 3.2 и которые на рис. 4.13 обозначены через С ₁ и С ₂ . Они могут быть описаны как множество

c ³+ 2с ²+ (1 — z)c + (1 — z) ²= 0,

где z изменяется в пределах круга радиуса 1/8 с центром в начале координат. Фактически, это уравнение дает нам не только обе эти «кляксы», но и «дочернюю» фигуру кардиоидной формы (основную часть рис. 3.1), которая находится слева на рис. 3.2 и которая обозначена как С ₃ на рис. 4.13. И, аналогично, эти области (как порознь, так и вместе) составляют рекурсивно нумеруемые множества благодаря существованию вышеприведенной формулы.

Несмотря на предположение о нерекурсивности множества Мандельброта, сделанное мной вначале, мы смогли разобраться с его наиболее значительными частями с помощью вполне определенного и достаточно простого алгоритма. Кажется, что такой процесс можно продолжать и дальше. Все наиболее очевидные области множества — и, конечно же, подавляющая часть множества (если не все оно целиком) в процентном выражении — поддаются алгоритмическому анализу. Если, как я предполагаю, все множество все-таки нерекурсивно, то те области, которые недоступны для действия алгоритма, должны быть с необходимостью очень «тонкими» и почти «невидимыми». Более того: когда мы найдем такую область, то вероятнее всего мы смогли бы понять, как нам изменить наш алгоритм, чтобы эта область также оказалась в зоне его действия. Однако, после этого найдутся другие области (если мое предположение о нерекурсивности справедливо), еще более труднодоступные из-за тонкости и сложности своей структуры, перед которыми будет бессилен даже наш усовершенствованный алгоритм. И вновь «волшебство» интуиции, искусства и техники, наверное, позволит нам вычленить эту область; но другие в очередной раз ускользнут от нас; и так будет повторяться снова и снова.

Я полагаю, что этот путь не слишком отличается от того, который часто используется в математике для решения трудных и, предположительно, нерекурсивных задач. Многие задачи, с которыми сталкиваются в некоторых специфических областях, часто решаются с помощью простых алгоритмических процедур — процедур, известных, быть может, на протяжении веков. Но некоторые из этих задач могут не поддаться таким методам, и тогда приходится искать более сложные пути к их решению. Такие задачи будут, конечно, сильнее всего интриговать математиков и подталкивать их к развитию все более мощных методов, в основу которых будет закладываться все более и более глубокое интуитивное понимание природы используемых математических объектов. Возможно, в этом есть что-то от того, как мы познаем окружающий нас физический мир.

В задачах покрытия и задачах со словами, рассмотренных выше, можно уже уловить, как применяется подобный подход (хотя это не те области математики, где аппарат развит в достаточной степени). Мы смогли привести очень простое доказательство для того, чтобы показать невозможность трансформации одного слова в другое при помощи установленных правил. Нетрудно вообразить, что более «продвинутые» методы доказательства способны помочь в более сложных случаях. Не исключена вероятность, что эти новые подходы могут быть превращены в алгоритмические процедуры. Мы знаем, что ни одна процедура не может удовлетворять всем примерам задачи со словами, но те из них, которые ускользают из «алгоритмических сетей», должны быть очень тонко и аккуратно сконструированы. Конечно, как только мы узнаем принцип построения таких примеров — как только мы будем уверены, что в неком конкретном случае произошла «осечка» алгоритма, — мы сможем усовершенствовать наш алгоритм так, чтобы он включал и этот частный пример. Ускользать могут только пары «неравных» слов, так что, как только мы находим такую «ускользающую» пару, мы можем быть уверены в их «неравенстве» и присовокупить этот критерий к нашему алгоритму. Так наше более глубокое понимание ведет ко все более совершенным алгоритмам!

Теория сложности

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

Теория сложности занимается не столько изучением трудностей, связанных с решением отдельных задач, сколько с бесконечными семействами задач, в каждом из которых любая задача может быть решена с помощью одного и того же алгоритма. Различные задачи такого семейства будут отличаться по «размеру», который выражается некоторым натуральным числом п. (Чуть позднее я объясню более подробно, как фактически этот номер п характеризует размер задачи.) Время, требуемое для решения конкретной задачи из рассматриваемого класса, — а вернее, количество элементарных шагов, — дается некоторым числом N , зависящим от n . Для определенности договоримся, что N — это наибольшее число шагов среди всех задач данного размера n , которое может понадобиться алгоритму для решения. При этом, с ростом n увеличивается также и N . На самом деле, N скорее всего будет расти гораздо быстрее n . Например, N может быть примерно пропорционально n ² , или n ³ или, скажем, 2 ⁿ (которое при больших n значительно превосходит n ², n ³ n ⁴, n ⁵ и, вообще, n ^r для любого фиксированного n ), или даже ₂ 2 ⁿ(которое, в свою очередь, растет еще быстрее).

Конечно, число «шагов» зависит от типа вычислительной машины, на которой применяется алгоритм. Если эта машина принадлежит классу машин Тьюринга, описанному в главе 2, у которых есть только одна лента — что довольно неэффективно — то число N может расти еще быстрее (или, эквивалентно, машина будет работать медленнее), чем в случае с двумя и более лентами. Чтобы избежать этих неопределенностей, вводится широкая классификация всех возможных зависимостей N ( n ), так что, независимо от типа используемой машины Тьюринга, величина темпов роста N будет всегда попадать в одну и ту же категорию. Одна из таких категорий, известная как Р (от названия «полиномиальное время»), включает все темпы роста, которые являются фиксированными кратными n или n ², n ³, n ⁴, n ⁵…. [91]. Это означает, что для любой задачи, попадающей в эту категорию Р (под «задачей» здесь фактически понимается семейство задач, решаемых с помощью единого алгоритма), будет справедлива оценка

N ≤ K x n ^r

где К и r — константы, не зависящие от n . То есть N не может быть больше, чем число, кратное n в некоторой фиксированной степени.

Простой, пример задачи, безусловно относящейся к Р , — перемножение двух чисел. Чтобы объяснить это, я должен сначала описать, как число n характеризует размер двух чисел, которые надо перемножить. Мы можем принять, что оба числа представлены в двоичной записи и что n / 2 — это просто количество бинарных разрядов в каждом из чисел, так что общее число цифр(то есть битов) у обоих равно n . (Если одно из чисел длиннее другого, то мы можем записать более короткое, начав с дополнительной последовательности нулей, тем самым выровняв их по длине.) Например, если n = 14, мы бы могли рассмотреть произведение

1011010 x 0011011,

которое является, на самом деле, произведением 1011010 х 11011, но с добавленными перед более коротким числом нулями. Выполнить требуемое действие проще всего путем умножения «в столбик»:

учитывая, что в двоичной системе 0x0=0, 0x1=0, 1x0=0, 1x1=1, 0+0=0, 0+1=1, 1+0=1, 1 + 1 = 10. Число отдельных двоичных перемножений равно (n/2) х (n/2) = n ²/4, а число отдельных двоичных сложений может доходить до n ²/4 — n/2 (включая перенос). Это дает n ²/2 — n/2 отдельных арифметических операций — и мы должны еще учесть несколько дополнительных логических шагов, которые задействованы в операциях переноса. Тогда общее число шагов, игнорируя члены более низкого порядка, равно по существу N = п ² /2, что, очевидно, является полиномом [92].

В общем случае, мы полагаем «размер» n задачи из некоторого класса равным полному количеству двоичных цифр (или битов), необходимых для задания свободных входных данных в задаче указанного размера. Другими словами, для произвольного размера n задача может иметь до 2 ⁿ различных вариантов (ибо для каждой из цифр имеется две возможности — 0 или 1, — а общее количество цифр равно n ), и все они должны одинаково обрабатываться алгоритмом не более, чем за N шагов.

Существует масса примеров (классов) задач, которые не «принадлежат» множеству Р . Например, чтобы вычислить ₂ 2 ^r для заданного натурального r , нам только для записи конечного ответа потребуется около 2 ⁿ шагов (где n — число цифр в двоичной записи r ), не говоря даже о самом вычислении. Операция по вычислению потребует уже ₂ 2 ⁿ шагов для записи и так далее. Значения этих выражений намного превосходят те, которые дают полиномы для тех же n , и, следовательно, не могут принадлежать Р .

Больший интерес представляют задачи, в которых ответ может быть записан и даже проверен на верность за «полиномиальное» время. Есть очень важная категория (алгоритмически решаемых классов) проблем, обладающих таким свойством. Их называют NP - задачами (классом задач). Точнее, если некоторая задача из класса NP имеет решение, то алгоритм позволит получить это решение, которое затем может быть проверено за «полиномиальное» время. Если же задача не имеет решения, то алгоритм сообщит об этом, но при этом не оговаривается необходимость проверки этого факта за «полиномиальное» или какое бы то ни было время [93].

NP - задачи встречаются во многих областях, причем как в математике, так и в повседневной практике. Я приведу здесь только один простой математический пример: задачу нахождения так называемого «гамильтонова цикла» на графе (довольно устрашающее название для чрезвычайно простой идеи). Под графом подразумевается конечный набор точек, или «вершин», некоторое количество пар которых соединено между собой линиями — «сторонами» графа. (Нас не интересуют сейчас геометрические или линейные свойства, а только то, какие вершины соединяются друг с другом. Поэтому не имеет значения, лежат ли все вершины в одной плоскости — если нас не волнует возможность пересечения двух сторон — или же в трехмерном пространстве.) Гамильтонов цикл — это замкнутый маршрут (петля), состоящий только из сторон графа и проходящий не более одного раза через любую из вершин. Пример графа с изображенным на нем гамильтоновым циклом показан на рис. 4.14. Задача нахождения гамильтонова цикла заключается в том, чтобы определить, существует ли гамильтонов цикл на рассматриваемом графе, и если существует, то явным образом указать его.

Есть разные способы представления графов на языке двоичных чисел. Неважно, какой из этих способов применяется в том или ином случае. Один из методов заключается в том, чтобы пронумеровать вершины 1, 2, 3, 4, 5…, а потом перечислить пары в некотором подходящем фиксированном порядке:

(1,2), (1,3), (2,3), (1,4), (2,4), (3,4), (1,5), (2, 5), (3,5), (4, 5), (1,6)….

Затем мы на место каждой пары помещаем «1», если пара соединена стороной графа, и «О» — в противном случае. Тогда двоичная последовательность

10010110110…

будет означать, что вершина 1 соединяется с вершинами 2, 4 и 5; вершина 3 — с вершинами 4 и 5; вершина 4 — с вершиной 5, и т. д. (в соответствии с рис. 4.14). Гамильтонов цикл может быть задан по желанию просто как подмножество этих сторон, которое было бы описано такой же двоичной последовательностью, как и ранее, но со значительно бо́льшим числом нулей. Процедура проверки в этом случае проходит несравненно быстрее, чем процесс непосредственного построения гамильтонова цикла. Все, что нужно выяснить, — это является ли построенный цикл действительно циклом, т. е. принадлежат ли его стороны исходному графу, и что каждая вершина графа используется ровно два раза — по одному разу на концах каждой из входящих в нее двух сторон.

Такую процедуру проверки можно легко завершить за «полиномиальное» время.

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

Другая задача, также являющаяся NP - полной [94]— «задача коммивояжера», которая во многом похожа на гамильтонов цикл, если не считать того, что разным сторонам приписаны числа и ставится цель отыскать гамильтонов цикл с минимальной суммой этих чисел (минимальной «длиной» пути, проделанного коммивояжером). Аналогично, «полиномиальное» время решения, достигнутое в «задаче коммивояжера», привело бы к возможности решать все NP - задачи за «полиномиальное» время. (Если такое решение когда-нибудь найдется, то новость об этом сразу попала бы на первые страницы! Ведь к NP - задачам относится, в частности, факторизация больших целых чисел, которая применяется в секретных шифровальных системах, представленных за последние несколько лет. Если эта задача окажется решаемой за «полиномиальное» время, то, возможно, такие шифры могли бы быть взломаны при помощи мощных современных компьютеров; если же нет — эти шифры останутся неприступными. См. Гарднер [1989].)

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

Сложность и вычислимость в физических объектах

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

Однако, я могу кардинально ошибаться по поводу важности той роли, которую играет сложность. Как будет показано позднее (глава 9, «Квантовые компьютеры»), теория сложности для реальных физических объектов, вероятно, может существенно отличаться от теории, изложенной мной ранее. Чтобы с уверенностью констатировать эту возможную разницу, необходимо будет использовать некоторые волшебные свойства квантовой механики — мистической, но все же поразительно точной теории, описывающей поведение атомов и молекул, а также и другие явления, многие из которых представляют интерес и на макромасштабах. Мы познакомимся с этой теорией в главе 6. Согласно ряду, идей, предложенных Давидом Дойчем [1985], существует принципиальная возможность построить «квантовый компьютер», на котором за «полиномиальное» время могут быть решены некоторые задачи (или классы задач), не принадлежащих Р . Пока совершенно неясно, как на практике сконструировать такое физическое устройство, которое бы (надежно) функционировало по принципу «квантового компьютера» — и, более того, рассматриваемый до сих пор класс задач носил заведомо искусственный характер, — но теоретически понятно, что квантовое физическое устройство могло бы улучшить работу машины Тьюринга.

А есть ли вероятность, что человеческий мозг, который в рамках данного обсуждения я рассматриваю как физическое устройство, хотя и имеющее чрезвычайно тонкую и сложную структуру — может неким образом использовать волшебство квантовой теории? Понимаем ли мы сегодня, как именно квантовые эффекты могут с пользой применяться для решения задач или формирования суждений? Можем ли мы представить, что для использования этих возможных преимуществ нам придется выйти «за нынешние пределы» квантовой теории? Насколько вероятно усовершенствование реальных физических устройств с учетом теории сложности для машин Тьюринга? И что говорит о таких устройствах теория вычислимости?

Чтобы рассматривать эти вопросы, нам надо будет отойти на время от математических абстракций и задаться целью выяснить в следующих главах, как же, в действительности, ведет себя окружающий нас мир!