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

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

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

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

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

В 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, по изложенной выше стратегии