Квантовые вычисления со времен Демокрита - Скотт Ааронсон

непротиворечива, вы никогда не сможете поймать их на противоречии. Смысл теоремы о полноте в том, что все бесконечное множество выдуманных чисел, которые выдают аксиомы, составит модель для 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]. Будьте уверены, мнения математиков об AC и CH до сего дня остаются разделенными, и высказано множество интересных аргументов как за, так и против них (которые у нас, к несчастью, нет времени разобрать подробно).

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

Дополнительный бонус

Какое отношение все это имеет к квантовой механике? Сейчас я сделаю героическую попытку обозначить для вас эту связь. До сих пор я старался убедить вас, что, если мы хотим считать мир непрерывным, это порождает глубочайшие сложности. Возьмите, к примеру, ручку: сколько различных позиций она может занимать на поверхности стола? ℵ1? Больше, чем ℵ1? Меньше, чем ℵ1? Мы не хотим, чтобы ответы на «физические» вопросы зависели от аксиом теории множеств!

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

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

Лично моя точка зрения состоит в том, что квантовую механику, как и классическую теорию вероятностей, следует рассматривать как в своем роде «промежуточную» между непрерывной и дискретной теорией. (Здесь я предполагаю, что гильбертово пространство[14] и пространство вероятностей имеет конечную размерность.) Я имею в виду, что, хотя непрерывные параметры существуют (соответственно амплитуды и вероятности), эти параметры невозможно наблюдать непосредственно, и это, в частности, «заслоняет» нас от странной вселенной аксиомы выбора и континуум-гипотезы. Нам не нужна разработанная физическая теория, чтобы признать физически бессмысленными вопросы о том, являются ли амплитуды рациональными или иррациональными и существует ли больше или меньше ℵ1 возможных амплитуд. Это непосредственно следует из того факта, что если бы мы хотели узнать точное значение амплитуды, то (даже если забыть об ошибках!) нам потребовалось бы измерить соответствующее состояние бесконечное число раз.

Упражнение

Пусть BB (n), или «n-е число Делового Бобра», — это максимальное число шагов, которые машина Тьюринга с n-состояниями может сделать на пустой первоначально ленте, прежде чем остановится. (Здесь максимум берется по всем машинам Тьюринга с n-состояниями, которые рано или поздно остановятся.)

1. Докажите, что BB (n) растет быстрее, чем любая вычислимая функция.

2. Пусть S = 1/BB (1) + 1/BB (2) + 1/BB (3) + …