Текст книги "Квантовые вычисления со времен Демокрита"

3. Гёдель, Тьюринг и все-все-все

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

Подумайте, что это означает. А означает это, что великую теорему Ферма, гипотезу Пуанкаре или любую другую математическую загадку, которая только придет вам в голову, можно доказать, начав с аксиом теории множеств, а затем применяя эти простенькие правила раз за разом, снова и снова. Вероятно, делать это придется 300 миллионов раз, но все же…

Как же Гёдель доказывает свою теорему о полноте? Доказательство описывают как «вывод семантики из синтаксиса». Мы просто придумываем объекты на заказ по мере того, как их требуют аксиомы! И если мы когда-нибудь наткнемся на несогласованность, то случиться это может лишь по одной причине: что несогласованность присутствовала и в первоначальных аксиомах.

Одним из немедленных следствий теоремы о полноте является теорема Лёвенгейма – Скулема: любой непротиворечивый набор аксиом имеет модель не более чем счетной мощности. (Заметим в скобках: если у вас в фамилии есть умляут, как у Лёвенгейма, – это одно из лучших предзнаменований успеха в математической логике.) Почему? Потому что процесс придумывания объектов, которые требуют аксиомы, может продолжаться даже если бесконечное, то все-таки счетное число шагов!

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

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

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

Но погодите! Разве теорема о неполноте не противоречит теореме о полноте, согласно которой, любое утверждение, которое следует из аксиом, может быть доказано исходя из этих аксиом? Придержите этот вопрос; мы проясним его чуть позже.

А сначала давайте посмотрим, как доказывается теорема о неполноте. Обычно говорят, что «доказательство теоремы о неполноте – это высший пилотаж математики, оно занимает 30 страниц и требует сложных построений с привлечением простых чисел», и т. п. Невероятно, но сегодня, через восемьдесят лет после Гёделя, это доказательство по-прежнему представлено в курсах математики именно так!

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

Где-то в средних классах школы у меня был приятель, который был очень силен в математике, но, возможно, не так уж силен в программировании. Он хотел написать программу с использованием массивов, но не знал, что такое массив. Что же он сделал? Каждому элементу массива он поставил в соответствие уникальное простое число, а затем их все перемножил; затем, когда ему требовалось считать из этого массива что-нибудь, он раскладывал это произведение на простые множители. (Если бы он программировал квантовый компьютер, не исключено, что такое решение было бы не самым неудачным!) Во всяком случае, мой приятель тогда делал, по существу, то же самое, что сделал Гёдель. Он придумал хитроумный ход, позволяющий программировать без программирования.

Машины Тьюринга

Так, пора выводить на сцену мистера Т.

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

Что эта машина может делать? Ну, очевидно, она должна уметь считывать символы с ленты и как-то модифицировать их в зависимости от того, что считывает. Для простоты будем считать, что машина считывает символы по одному. Но в таком случае было бы лучше, если бы она умела двигаться по ленте вперед и назад. Было бы также хорошо, если бы после того, как ответ вычислен, она могла бы остановиться! Но встает вопрос: как в любой данный момент машина должна решать, что ей делать? Согласно Тьюрингу, это решение должно зависеть только от двух фрагментов информации: (1) считываемого в настоящий момент символа и (2) текущей «внутренней конфигурации» машины, ее «состояния». На основе внутреннего состояния и считываемого символа машина должна (1) записать какой-то новый символ в текущей клеточке, заменив им тот символ, который находился там прежде (2) сдвинуться по ленте вперед или назад на одну клеточку и (3) переключиться в новое состояние или остановиться.

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

Первым результатом Тьюринга было существование «универсальной» машины – машины, работа которой состоит в моделировании любой другой машины, описанной посредством символов на ленте. Иными словами, могут существовать универсальные программируемые вычислители. Нет нужды строить отдельную машину для обслуживания электронной почты, отдельную для проигрывания DVD-дисков, еще одну для игры в Tomb Raider и т. п.: можно построить одну-единственную машину, которая будет моделировать любую специализированную машину, выполняя различные программы, которые хранятся в памяти. Но этот вывод даже не был основным результатом знаменитой статьи Тьюринга.

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

Одним из свидетельств того, что эта проблема может оказаться непростой, является тот факт, что если бы могли ее решить, то мы также могли бы решить многие знаменитые нерешенные математические задачи. Так, гипотеза Гольдбаха утверждает, что любое четное число, равное или большее 4, может быть записано в виде суммы двух простых. Мы, понятно, можем написать программу, которая будет проверять числа 4, 6, 8 и т. п. и остановится только в том случае, если найдет четное число, которое не может быть записано в виде суммы двух простых чисел. Решение вопроса о том, остановится ли когда-либо эта программа, будет эквивалентно выяснению вопроса об истинности или ложности гипотезы Гольдбаха.

Но можем ли мы доказать, что не существует программы, которая решила бы проблему остановки? Именно это и сделал Тьюринг. Его ключевая идея заключается в том, чтобы даже не пытаться анализировать внутреннюю динамику такой программы, если бы она существовала. Вместо этого он просто говорит: предположим, для создания противоречия, что такая программа P существует. Тогда мы можем модифицировать P так, чтобы получить при этом новую программу P′, которая делает следующее. Получив на вход еще одну программу Q, программа P′

1. Работает вечно, если Q останавливается при получении на вход собственного кода, или

2. Останавливается, если Q работает вечно при получении на вход собственного кода.

Теперь мы просто подаем P′ на вход ее собственный код. Согласно приведенным условиям, P′ будет работать вечно, если остановится, или остановится, если будет работать вечно. Следовательно, P′ – и, как следствие, P – вообще не может существовать.

Как я уже сказал, если у нас есть результаты Тьюринга, то результаты Гёделя мы получим бесплатно, в качестве бонуса. Почему? Ну предположим, что теорема о неполноте ошибочна, то есть что существует непротиворечивая вычислимая система доказательства F, на основании которой любое высказывание о целых числах можно либо доказать, либо опровергнуть. Тогда, получив произвольную компьютерную программу, мы могли бы просто начать поиск по всем возможным доказательствам в F и искать до тех пор, пока не обнаружили бы доказательство либо того, что программа остановится, либо того, что она не остановится никогда. Это возможно, ведь утверждение о том, что какая-то конкретная программа остановится, в конечном итоге представляет собой именно высказывание о целых числах. Но это дало бы нам алгоритм решения проблемы остановки, а мы уже знаем, что решить ее невозможно. Следовательно, F не может существовать.

Обдумав все это более тщательно, мы можем выжать даже более сильный результат. Пусть P – программа, которая, получив на вход другую программу Q, пытается решить, остановится ли Q, по изложенной выше стратегии (то есть путем перебора всех возможных доказательств и опровержений высказывания о том, что Q остановится, в некоей формальной системе F). Тогда, как в доказательстве Тьюринга, предположим, что мы модифицируем P и получим новую программу P′, такую, что она

1. Работает вечно, если доказано, что Q при получении на вход собственного кода останавливается, или

2. Останавливается, если доказано, что Q при получении на вход собственного кода работает вечно.

Далее предположим, что мы подаем на вход P′ ее собственный код. В этом случае мы знаем, что P′ будет работать вечно и никогда не обнаружит доказательства или опровержения высказывания о том, что она остановится. Ибо если P′ найдет доказательство того, что остановится, то она будет работать вечно, а если она найдет доказательство того, что будет работать вечно, то остановится, а это противоречие.

Но здесь присутствует очевидный парадокс: почему приведенный аргумент не является сам по себе доказательством того, что P′, получив на вход собственный код, будет работать вечно? И почему P′ не может найти доказательство того, что она будет работать вечно, – и, следовательно, остановится, и, следовательно, работать вечно, и, следовательно, остановится и т. п.?

Ответ в следующем: при «доказательстве» того, что P′ будет работать вечно, мы сделали скрытое предположение, а именно что система доказательства F непротиворечива. Если бы условия непротиворечивости не было, то вполне могло бы существовать доказательство того, что P′ остановится, хотя в реальности P′ работала бы вечно.

Но это означает, что если F могла бы доказать, что F непротиворечива, то F могла бы также доказать, что P′ будет работать вечно, – и таким образом вновь вытащила бы на свет божий приведенное выше противоречие. Из всего этого можно сделать единственный вывод: если система F непротиворечива, то F не может доказать собственную непротиворечивость. Этот результат иногда называют второй теоремой Гёделя о неполноте.

Вторая теорема о неполноте устанавливает то, что нам, вероятно, следовало ожидать с самого начала: что математические теории, достаточно напыщенные, чтобы доказывать собственную непротиворечивость, не могут на самом деле похвастать этой самой непротиворечивостью! Если мы хотим доказать, что теория F непротиворечива, то сделать это мы можем только в рамках другой, более мощной теории; в качестве тривиального примера можно привести F + Con(F) (теория F плюс аксиома о непротиворечивости F). Но как мы можем знать, что F + Con(F) само по себе непротиворечиво? Ну, мы можем доказать это только в рамках еще более сильной теории: F + Con(F) + Con(F + Con(F)) (это F + Con(F) плюс аксиома о том, что F + Con(F) непротиворечива). И так до бесконечности. (И даже дальше, чем до бесконечности, в область счетных ординальных чисел.)

Возьмем конкретный пример: вторая теорема о неполноте говорит нам, что самая популярная система аксиом для целых чисел, арифметика Пеано, не может доказать собственной непротиворечивости. Или, в символьной форме, PA не может доказать Con (PA). Если мы хотим доказать Con (PA), нам необходимо перейти к более сильной системе аксиом, такой как ZF (аксиомы теории множеств Цермело – Френкеля). В системе ZF мы можем доказать Con (PA) без особого труда, использовав аксиому бесконечности для конструирования бесконечного множества, которое затем служит моделью PA.

С другой стороны, опять же согласно второй теореме о неполноте, ZF не может доказать свою собственную непротиворечивость. Если мы хотим доказать Con (ZF), то простейший способ сделать это – постулировать существование бесконечностей больших, чем все, что может быть определено в рамках ZF. Такие бесконечности называют большими кардинальными числами. (Если уж специалисты по теории множеств говорят про что-то, что оно «большое», то оно действительно большое.) Опять же мы можем доказать непротиворечивость ZF в рамках системы ZF + LC, где LC – это аксиома существования больших кардинальных чисел. Но если мы хотим доказать, что сама система ZF + LC непротиворечива, то нам потребуется еще более мощная теория, к примеру с бесконечностями, которые будут еще больше.

Быстрый вопрос на понимание: хотя мы не можем доказать Con(PA) в рамках PA, можем мы хотя бы доказать в рамках PA, что из Con(PA) следует Con(ZF)?

Нет, не можем. Потому что тогда мы могли бы также доказать в рамках ZF, что из Con(PA) следует Con(ZF). Но поскольку в ZF можно доказать Con(PA), это означало бы, что в ZF можно доказать Con(ZF), что противоречит второй теореме о неполноте.

Я обещал объяснить, почему теорема о неполноте не противоречит теореме о полноте. Проще всего, вероятно, сделать это через пример. Рассмотрим «самоненавистническую теорию» PA + не (Con(PA)), то есть арифметику Пеано плюс утверждение о ее противоречивости. Нам известно, что если PA непротиворечива, то эта странная теория тоже должна быть непротиворечива, поскольку в противном случае PA доказала бы свою непротиворечивость, чего теорема о неполноте не позволяет. Из этого следует, согласно теореме о полноте, что PA + не (Con(PA)) должна иметь модель. Но как такая модель могла бы выглядеть? В частности, что произошло бы, если бы вы в рамках этой модели просто захотели бы увидеть доказательство противоречивости PA?

Я скажу вам, что произошло бы: аксиомы сказали бы вам, что доказательство противоречивости PA зашифровано некоторым положительным целым числом X. После чего вы сказали бы: «Но что такое X?» И аксиомы сказали бы: «X». А вы сказали бы: «Но что есть X как обычное положительное целое число?»

– Что вы имеете в виду под обычным положительным целым числом?

– Я имею в виду – не какая-то абстрактная сущность, обозначенная каким-то символом, к примеру X, но 1, или 2, или 3, или какое-то другое конкретное целое число, которое получается, если начать с 0 и прибавить 1 конечное число раз.

– Что вы имеете в виду, говоря «конечное число раз»?

– Я имею в виду, ну, один раз, или два, или три раза…

– Но тогда ваше определение образует замкнутый круг!

– Послушайте, вы прекрасно знаете, что я имею в виду, говоря «конечный»!

– Нет-нет-нет! Говорите на языке аксиом.

– Ну хорошо, это ваше X больше или меньше 10^{500 000}?

– Больше. (Аксиомы не глупы и понимают, что если они скажут «меньше», вы сможете просто проверить все меньшие числа и убедиться, что ни в одном из них не зашифровано доказательство противоречивости PA.)

– Так, ладно, что есть X + 1?

– Y.

И так далее. Аксиомы будут и дальше выдавать на ваши запросы всевозможные выдуманные числа, и, считая, что PA непротиворечива, вы никогда не сможете поймать их на противоречии. Смысл теоремы о полноте в том, что все бесконечное множество выдуманных чисел, которые выдают аксиомы, составит модель для PA, но не обычную модель (какой могли быть, к примеру, обычные положительные целые числа)! Если же мы будем настойчиво продолжать разговор об обычной модели, то автоматически перейдем из владений теоремы о полноте во владения теоремы о неполноте.

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

Положим для определенности, что теорема, которую мы хотим доказать, – это гипотеза Римана (RH), а формальная система, в рамках которой мы хотим ее доказывать, – это теории множеств Цермело – Френкеля (ZF). Предположим, что мы в состоянии доказать в ZF, что если ZF доказывает RH, то RH верна. Тогда, взяв контрапозитивное высказывание, мы можем доказать также в рамках ZF, что если RH ложна, то ZF не доказывает RH. Иными словами, мы можем доказать в рамках системы ZF + не (RH), что не (RH) полностью согласуется с ZF. Но это означает, что теория ZF + не (RH) доказывает собственную непротиворечивость, а это, по Гёделю, означает, что система ZF + не (RH) противоречива. Но сказать, что ZF + не (RH) противоречива, – это все равно что сказать, что RH есть теорема из ZF. Следовательно, мы доказали RH. В общем, мы обнаруживаем, что если некоторое утверждение может быть доказано принятием аксиомы о том, что оно доказуемо, то оно может также быть доказано и без принятия такой аксиомы. Результат известен как теорема Лёба (опять фамилия с умляутом – Löb), хотя лично мне кажется, что лучше было бы назвать ее теоремой «вы-и-без-того-все-знали».

А помните, чуть раньше мы говорили об аксиоме выбора и континуум-гипотезе? Это естественные высказывания о континууме, которые, поскольку континуум является столь хорошо определенной математической сущностью, непременно должны быть либо истинными, либо ложными. А как вообще разрешаются подобные вещи? Гёдель доказал в 1939 г., что принятие аксиомы выбора (AC) или континуум-гипотезы (CH) не может привести ни к какому противоречию. Иными словами, если бы теории ZF + AC или ZF + CH оказались противоречивы, то только потому, что противоречива сама ZF.

В связи с этим возник очевидный вопрос: можем ли мы принять ложность AC и CH и тоже не получить никакого противоречия? Гёдель работал над этой проблемой, но не сумел получить ответ. Наконец, Пол Коэн в 1963 г. дал положительный ответ, придумав при этом новую технику – «форсинг». (За это он был удостоен единственной медали им. Филдса, выданной когда-либо за работу в области теории множеств и оснований математики.)

Итак, мы теперь знаем, что обычные аксиомы математики не позволяют определить истинность или ложность аксиомы выбора и континуум-гипотезы. Вы вольны верить в то, что обе они истинны, обе ложны или истинна только одна, и не бояться никаких противоречий[13]13
  Аналогично тому, как можно построить непротиворечивые варианты геометрии, включив в число аксиом евклидову аксиому о параллельных либо ее отрицание.


[Закрыть]. Будьте уверены, мнения математиков об AC и CH до сего дня остаются разделенными, и высказано множество интересных аргументов как за, так и против них (которые у нас, к несчастью, нет времени разобрать подробно).

Позвольте мне закончить наблюдением, которое, возможно, удивит вас: независимость AC и CH от теории множеств ZF сама по себе является теоремой арифметики Пеано. Ибо, в конечном итоге теоремы Гёделя и Коэна о непротиворечивости сводятся к комбинаторным утверждениям о манипуляциях с высказываниями первого порядка, которые в принципе могут быть доказаны непосредственно, без каких бы то ни было размышлений о трансфинитных множествах, которые эти высказывания, по идее, описывают. (На практике перевести эти результаты в комбинаторику было бы ужасающе сложно, и Коэн говорил, что попытка поразмышлять об этих проблемах в конечных комбинаторных терминах никуда его не привела. Однако мы знаем, что в теории это можно сделать.) Это прекрасно иллюстрирует то, что представляется мне центральным философским вопросом всего этого дела: говорим ли мы на самом деле когда-нибудь о континууме или только о конечных последовательностях символов, которые говорят о континууме?