Поиск первоисточников
АрхивСтатья представляет собой слегка "причесанную" запись заочной дискуссии, происходившей некоторое время назад, когда Тема номера только замышлялась и шла "обкатка" концепции. Участники дискуссии: Михаил Вялый, Марк Шнайдер, Олег Берестовой, а также ваш покорный слуга.
Статья представляет собой слегка «причесанную» запись заочной дискуссии, происходившей некоторое время назад, когда Тема номера только замышлялась и шла «обкатка» концепции. Участники дискуссии: Михаил Вялый (его статьи опубликованы в этом номере); Марк Шнайдер, доктор физ.-мат. наук, начальник отдела ННТЦ «Луч»; Олег Берестовой - заместитель директора по науке НПО «Орбита», доктор технических наук; а также ваш покорный слуга. Стремясь сохранить своеобразный колорит живого общения (пусть даже при помощи e-mail), я не стал редактировать стиль и убирать шутки и колкости в адрес оппонентов. В общем, репортаж «из кухни».
Давайте поговорим о квантовых алгоритмах. Они ведь совсем не похожи на обычные, и это мало кому известно.
МВ: Вся штука в том, что никто не знает, на что они похожи. Кроме того, за последние пять лет прогресс в области эффективных квантовых алгоритмов столь незначителен, что можно говорить о тупике. Есть косвенные теоретические доводы, говорящие, что этот тупик неслучаен.
Вы не смогли бы немного просветить меня на этот счет? Упомянуть хотя бы об основных идеях и, если можно, дать ссылки.
МВ: Доводы, о которых я упоминал, - косвенные. Они относятся не к конкретным задачам, а к сложностным классам. То есть доводы в пользу того, что класс эффективных квантовых алгоритмов (BQP) не содержит никаких интересных сложностных классов, кроме BPP (эффективных вероятностных алгоритмов). Во всяком случае, так обстоит дело в релятивизованных мирах (то есть при вычислениях по модулю некоторого оракула - когда вычисление некоторой функции дается бесплатно).
Одна из статей на эту тему: C.Bennett, E.Bernstein, G.Brassard, U.Vazirani, «Strengths and weaknesses of quantum computing», SIAM J. On Comput, 26(5), 1997, p. 1510-1523. Из существования релятивизованных миров, в которых BQP узок, следует, что идеи типа «сокращения перебора» (как в алгоритме Гровера) не работают в квантовом случае.
Другая работа - L.Fortnow, J.Rogers «Complexity Limitations on Quantum Computation» архив xxx.lanl.gov, номер в архиве cs.CC/9811023. В ней помимо различных оракульных утверждений доказывается также, что BQP is low for PP. Это означает, что добавление языков BQP в качестве оракулов к классу PP не расширяет класс PP (а вообще-то, PP с оракулами из PP, по-видимому, гораздо сильнее).
Такого рода доводы в теории сложности широко распространены: почти ничего доказать пока не удается. Конечно, их косвенный характер оставляет место для различных прогнозов. Оптимисты надеются на какие-нибудь очень нетривиальные идеи. Но если говорить не о надеждах, а о достижениях, то ничего принципиально нового за последние пять лет не появилось. Идет медленное дожимание старых идей… Я имею в виду именно эффективные алгоритмы. А время от времени появляются сильные и интересные результаты в области квантовых вычислений. Но они либо относятся к более сложным классам, либо дают новые характеризации BQP.
Кстати, о вероятностях… Существует точка зрения, что поскольку нельзя придумать алгоритм, генерирующий абсолютно случайные события, а они все же имеют место в нашем мире, то это говорит о некоторых фундаментальных ограничениях применимости математики.
МВ: Математика и алгоритмы - разные вещи. Вообще-то, никакой алгоритм (детерминированный) не может генерировать случайные величины по определению. Алгоритм (в сколько-нибудь обычном понимании этого слова) может выдавать последовательности символов.
И есть устройства, алгоритмами не являющиеся. Но их тоже можно описывать на языке математики. Так что мне не очень понятно, в чем вопрос. Во всяком случае, если говорить о фундаментальных ограничениях применимости математики, то мне известно лишь одно - несообразительность (сообразил - значит, применил).
Насчет устройств, алгоритмами не являющихся. Мы вплотную подошли к интересной проблеме, которую, не помню уже кто, назвал «проблемой элементарного вычислителя». Речь о том, что любой алгоритм, вообще говоря, предполагает наличие его исполнителя - «вычислителя», который является физическим объектом и функционирование которого можно описать опять же в терминах выполнения некоторого «алгоритма-прим» и т. д. В определенном смысле - это проблема курицы и яйца. Что чему предшествует? Какова точка зрения математики?
МВ: Я вообще не понимаю этого вопроса. Его вроде бы не существует с точки зрения математики. Любой алгоритм формулируется для некоторого вычислителя. То есть доказывается, что можно сделать то-то и то-то, если возможны такие-то элементарные действия. В математике вообще все утверждения носят условный характер: если выполнено условие, то справедливо заключение. По-моему, только это и придает утверждениям математики объективную истинность (но я предпочел бы не спорить по этому поводу с философами, поскольку не нуждаюсь в определении объективности). Во всяком случае, безусловные объективные истины мне не известны.
Если смотреть на вещи прагматически, то элементарные вычислители - это те или иные природные процессы. Поэтому их нужно описывать не на языке алгоритмов, а проверять методами естественных наук (гипотеза, эксперимент) законы их функционирования.
МШ: Па-а-звольте!
Не позволю. (шутка)
МШ: Юрий, вы сказали, что «алгоритм выполняется неким физическим процессором», верно? Так вот, это не упущение математиков. Это нечто другое, из «другой оперы». Ведь математика «в чистом виде» - вещь невозможная. Все мы (и математика тоже) реализованы в физическом мире и при посредстве возможностей и свойств этого мира.
Вообще-то, мне кажется, я понимаю вашу мысль. Как баллистик, я бы ее переформулировал так: когда бутерброд падает на брюки с ускорением g, траектория и параметры его движения определяются законами физики, но ведь можно же организовать точно такое же движение при помощи системы управления, то есть алгоритмически. Для внешнего наблюдателя оба процесса будут одинаковы. В этом смысле любые природные процессы можно рассматривать как следствия работы алгоритмов, однако и они, в свою очередь, должны «на чем-то работать».
Вам бы с Арнольдом пообщаться, но вряд ли получится. Разве что имидж «Компьютерры» поможет. Неплохой имидж, прямо скажу. Попытайтесь…
Понимаете, нет ничего такого, что существует само по себе, вне физики. В этом смысле математика - тоже физика. Все, что мы видим в математике, предполагает наличие физики, которая выступает в качестве того самого процессора, о котором вы упоминали. Другой вопрос - как этот процессор устроен?
ОБ: Марк Исаакович - хороший человек. Уже потому, что не берется вам растолковать, как устроена физика. А ведь мог бы!.. Снимаю шляпу. Но насчет физики - неубедительно.
Дело в том, что наше время подарило нам такую глубоко философскую вещь, как компьютерные игры…
О да!.. Особенно «шутеры».
ОБ: Перестаньте. Философичность игр не в их содержании, а в самом факте их существования. Если не принимать во внимание ограниченность технических средств, то ведь не существует никаких принципиальных ограничений на создание игр столь сложных и многоплановых, что их, строго говоря, уже нельзя будет называть играми. Это будут Миры!
Теперь вообразите, что эту работу уже кто-то проделал и все мы, вся наша математика и физика, - просто система, совокупность множества алгоритмов, непрерывно выполняющихся неким процессором. Эти алгоритмы непрерывно взаимодействуют друг с другом, порождая «кажимость», иллюзию объектов и их взаимодействий. Хотя «внутри» - никакой иллюзии нет. Есть объекты, их свойства, динамика и т. п. Строго говоря, вся физика может быть представлена как «конечный продукт работы» чрезвычайно сложной системы взаимодействующих алгоритмов.
А как же физическая природа того процессора, который все эти алгоритмы выполняет?
МШ: Это вы его, Юра, уели! Слышите, Олег Яковлевич, что вам молодой человек говорит?
ОБ: Двое на одного? А я и не утверждаю, что знаю физику работы того процессора. Я говорю, что «наша» физика вполне может оказаться не единственной. «Внутри» компьютерной игры мы можем реализовать множество различных физик чисто алгоритмическими методами. И множество логик. И целую кучу математик.
А что до процессоров, то они, ясное дело, находятся в том мире, в котором находятся, и функционируют по законам «той» физики.
А «та» физика, в свою очередь, реализована компьютерами «свыше» и т. д.?
МШ: Точно! Юрий, вы же видите, что О.Я. просто стесняется называть вещи своими именами. Все, что он говорит, - это же гипотеза о Всевышнем! О Боге, который и есть владелец тех компьютеров и алгоритмов. Это ж ясно как день!..
ОБ: Отнюдь! Я не согласен категорически! Причем тут Бог? Говоря о «компьютерах», я имел в виду возможность существования некоторого фи-зи-чес-ко-го процесса, динамика параметров которого может быть интерпретирована в терминах обработки данных и, следовательно, - выполнения алгоритмов. Вот этот процесс, видимо, и можно было бы назвать «элементарным вычислителем». Но что представляет собой этот процесс, сегодня, как мне кажется, никто сказать не может. Это ведь должен быть какой-то действительно элементарный процесс, несводимый к другим. Думаю, на его роль может претендовать черная дыра. Вот уж, воистину, ни к чему «нашему» ее внутренние дела не сводимы. А «на выходе» у нее - еще одно элементарное, фундаментальное явление (или процесс) - абсолютная случайность.
Олег Яковлевич, не раскрывайте карты. Об этих вещах я вас приглашаю поговорить в другой Теме - о фундаментальных взаимосвязях физики и математики. Так что потерпите немного.
ОБ: Потерплю, потерплю. Кстати, говоря о несводимости элементарных процессов к другим прочим, уместно вспомнить, что в отношении алгоритмов существует гипотеза о возможности построения своего рода «гармонического разложения» алгоритмов в базисе периодически исполняемых процедур (которые здесь играют роль «элементарных процессов»), что даст возможность строить приближенные алгоритмы-модели «неалгоритмизируемых» процессов, осуществлять «фильтрацию» свойств алгоритмов и т. п.
И существует такое направление, как теория языков программирования. Насколько мне известно, там рассматриваются операции над алгоритмами как некоторыми объектами…
МВ: Такая дисциплина действительно существует (кажется, она еще называется логическим программированием). Операции там производятся скорее над программами, чем над алгоритмами, хотя разница не очень большая. В сущности, программа - это формальное выражение понятия «алгоритм». Можно ли применять такие вещи к анализу неалгоритмизируемых процессов, я не знаю. Честно говоря, мне кажется, что неалгоритмизируемые процессы почти всегда оказываются и неформализуемыми. А тогда довольно опасно заранее решать, как именно их моделировать. Меня приучили к мысли, что вначале должна быть адекватная формализация, а все остальное - потом.
МШ: Так вы действительно хотите посвятить тему номера фундаментальным случайностям, или Олег Яковлевич что-то напутал? Он тут меня уговаривает написать с ним в соавторстве статью…
Ну, если не всю Тему, то хотя бы часть ее. Пишите, буду рад получить от вас что-нибудь о вашей работе 1. Всего вам доброго! И удачи!
1 (обратно к тексту) - Специально повторяю для читателей: пишите! Буду рад получить от вас что-нибудь о вашей работе. Всего доброго! И удачи! - Ю.Р.
