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

class="p1">Является ли S вычислимым действительным числом? Иными словами, существует ли алгоритм, который, получив на вход положительное целое число k, выдаст на выходе рациональное число S′, такое, что |S — S′| < 1/k?

Дополнительная литература

Прекрасным дополнением материала этой главы может стать книга Торкеля Францена «Теорема Гёделя. Неполный путеводитель по ее правильному и неправильному использованию» (Gödel's Theorem: An Incomplete Guide to its Use and Abuse, by Torkel Franzén: A. K. Peters Ltd, 2005).

4. Разум и машины

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

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

Судя по всему, первым оракулы исследовал Тьюринг в 1938 г. в своей диссертации на степень доктора философии. Очевидно, всякий, кто способен написать целую диссертацию об этих воображаемых сущностях, должен быть чрезвычайно чистым теоретиком — человеком, который ни за что на свете не хотел бы заниматься чем-то практически полезным. В случае Тьюринга это, безусловно, так и было, — в самом деле, несколько лет после защиты докторской диссертации, с 1939 по 1943 г., он потратил на изучение некоторых мудреных преобразований симметрии в 26-буквенном алфавите[15].

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

Далее, степень Тьюринга, или степень неразрешимости, составляют множество всех задач, эквивалентных по Тьюрингу некоей данной задаче. Можно ли привести примеры степени неразрешимости? Мы с вами уже видели два таких примера: это (1) множество вычислимых задач и (2) множество задач, эквивалентных по Тьюрингу проблеме остановки. Сказать, что эти степени неразрешимости не равны, — все равно что сказать, что проблема остановки неразрешима.

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

А вот более тонкий вопрос: существует ли задача промежуточной сложности между множеством вычислимых задач и задачей остановки? Этот вопрос первым задал Эмиль Пост в 1944 г., а ответили на него в 1954 г. Пост и Стивен Клини (хотя в первоначальной формулировке задачи у Поста было добавлено дополнительное условие, названное «рекурсивной перечислимостью», и только два года спустя Ричард Фридберг и Альберт Мучник показали, как можно его выполнить). Ответ был «да». На самом деле у нас есть и более сильный результат: существуют две задачи A и B, каждая из которых разрешима при наличии оракула для проблемы остановки, но ни одна из них не разрешима при наличии оракула для другой. Эти задачи строятся посредством бесконечного процесса, цель которого — устранить любую машину Тьюринга, способную свести A к B или B к A. К несчастью, получающиеся в результате задачи выглядят в высшей степени неестественно; не похоже, что что-то подобное может возникнуть на практике. И даже сегодня у нас нет ни единого примера «естественной» задачи с промежуточной степенью неразрешимости.

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

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

Возникает очевидный вопрос: к какому классу отнести это утверждение? Быть может, это эмпирическое утверждение о том, какие функции могут быть вычислены в физической реальности? Или это определение, объясняющее смысл слова «вычислимый»? Или то и другое понемногу?

Как бы то ни было, тезис Чёрча — Тьюринга можно считать чрезвычайно успешным представителем тезисов. Как вам известно, — и мы поговорим об этом позже, — квантовые вычисления представляют серьезный вызов для так называемого «расширенного тезиса Чёрча — Тьюринга»: что любая функция, которую естественно рассматривать как эффективно вычислимую, является эффективно вычислимой на машине Тьюринга. Но, на мой взгляд, оригинальный тезис Чёрча — Тьюринга