Новый ум короля: О компьютерах, мышлении и законах физики
Шрифт:
(1,2), (1,3), (2,3), (1,4), (2,4), (3,4), (1,5), (2, 5), (3,5), (4, 5), (1,6)….
Затем мы на место каждой пары помещаем «1», если пара соединена стороной графа, и «О» — в противном случае. Тогда двоичная последовательность
10010110110…
будет означать, что вершина 1 соединяется с вершинами 2, 4 и 5; вершина 3 — с вершинами 4 и 5; вершина 4 — с вершиной 5, и т. д. (в соответствии с рис. 4.14). Гамильтонов цикл может быть задан по желанию просто как подмножество этих сторон, которое было бы описано такой же двоичной последовательностью, как и ранее, но со значительно большим числом нулей. Процедура проверки в этом случае проходит несравненно быстрее, чем процесс непосредственного построения гамильтонова цикла. Все, что нужно выяснить, — это является ли построенный цикл действительно циклом, т. е. принадлежат ли его стороны исходному графу, и что каждая вершина графа используется ровно два раза — по одному разу на концах каждой из входящих в нее двух сторон.
Такую процедуру проверки можно легко завершить за «полиномиальное» время.
На самом деле эта задача относится не только к NP , но к так называемой категории NP – полных задач.
Другая задача, также являющаяся NP – полной [94] — «задача коммивояжера», которая во многом похожа на гамильтонов цикл, если не считать того, что разным сторонам приписаны числа и ставится цель отыскать гамильтонов цикл с минимальнойсуммой этих чисел (минимальной «длиной» пути, проделанного коммивояжером). Аналогично, «полиномиальное» время решения, достигнутое в «задаче коммивояжера», привело бы к возможности решать все NP – задачиза «полиномиальное» время. (Если такое решение когда-нибудь найдется, то новость об этом сразу попала бы на первые страницы! Ведь к NP – задачамотносится, в частности, факторизация больших целых чисел, которая применяется в секретных шифровальных системах, представленных за последние несколько лет. Если эта задача окажется решаемой за «полиномиальное» время, то, возможно, такие шифры могли бы быть взломаны при помощи мощных современных компьютеров; если же нет — эти шифры останутся неприступными. См. Гарднер [1989].)
94
Строго говоря, нам нужно переформулировать эту задачу под ответ «да или нет», например: существует ли маршрут для коммивояжера, длина которого меньше чем столько-то? (См. предыдущее примечание.)
Эксперты, как правило, полагают, что используя устройство, работающее по принципу машины Тьюринга, невозможно за «полиномиальное» время решить NP – полнуюзадачу; и что, следовательно, Р и NP — неэквивалентны. Это мнение, похоже, верно, хотя пока его никто не смог доказать. И это остается наиболее важной и на сегодняшний день нерешенной задачей теории сложности.
Сложность и вычислимость в физических объектах
Теория сложности является важной для наших рассуждений в этой книге не только потому, что она касается вопроса возможности алгоритмизации, но и потому, что она позволяет для заведомо алгоритмизуемых объектов решать вопрос о том, могут ли использоваться соответствующие алгоритмы на практике. В последующих главах я буду больше говорить о вычислимости, чем о теории сложности, поскольку я склонен думать (хотя, конечно, и не имея для этого достаточных оснований), что, в отличие от фундаментального вопроса вычислимости, положения теории сложности не настолькр значимы для феномена мышления. Более того, мне представляется, что теория сложности сегодня лишь слегка затрагивает вопросы практичности алгоритмов.
Однако, я могу кардинально ошибаться по поводу важности той роли, которую играет сложность. Как будет показано позднее (глава 9, «Квантовые компьютеры»), теория сложности для реальных физических объектов, вероятно, может существенно отличаться от теории, изложенной мной ранее. Чтобы с уверенностью констатировать эту возможную разницу, необходимо будет использовать некоторые волшебные свойства квантовой механики — мистической, но все же поразительно точной теории, описывающей
А есть ли вероятность, что человеческий мозг, который в рамках данного обсуждения я рассматриваю как физическое устройство, хотя и имеющее чрезвычайно тонкую и сложную структуру — может неким образом использовать волшебство квантовой теории? Понимаем ли мы сегодня, как именно квантовые эффекты могут с пользой применяться для решения задач или формирования суждений? Можем ли мы представить, что для использования этих возможных преимуществ нам придется выйти «за нынешние пределы» квантовой теории? Насколько вероятно усовершенствование реальных физических устройств с учетом теории сложности для машин Тьюринга? И что говорит о таких устройствах теория вычислимости?
Чтобы рассматривать эти вопросы, нам надо будет отойти на время от математических абстракций и задаться целью выяснить в следующих главах, как же, в действительности, ведет себя окружающий нас мир!
Глава 5
Классический мир
Состояние физической теории
Что нам нужно знать о законах природы, чтобы понять, какая роль в ней может быть отведена сознанию? Насколько важно представлять себе для этого принципы организации и взаимодействия, которым подчиняются элементы, составляющие тело и мозг? Если осознанное восприятие — всего лишь результат выполнения алгоритмов (как нас пытаются убедить многие приверженцы ИИ), то вопрос о конкретном виде и действии этих принципов не имеет особого значения. Любое устройство, способноепросчитать алгоритм, будет ничуть не хуже любого другого. Но, быть может, наше чувство осознания не сводится полностью к работе алгоритмов. И возможно, что детальное знание нашего внутреннего устройства и точных физических законов, управляющих той субстанцией, из которой мы состоим, может оказаться достаточно важным. Вероятно, нам понадобиться понять те фундаментальные физические свойства, которые лежат в основе самой природы вещества и определяют его поведение. Сегодня физика не достигла пока такого уровня, и ей предстоит еще раскрыть множество тайн и испытать немало глубоких озарений. Тем не менее большинство физиков и физиологов склонны считать, что мы уже сейчасрасполагаем достаточным знанием тех физических законов, которые управляют работой такого объекта средних размеров, как наш мозг. Хотя никто не оспаривает исключительную сложность головного мозга человека как физической системы и не отрицает существования значительного числа пробелов в наших знаниях о его детальной структуре и принципах работы, — все же лишь немногие осмелились бы утверждать, что мы испытываем существенную нехватку знаний именно в области физическихоснов функционирования мозга.
Ниже я приведу пример, свидетельствующий как раз об обратном, — то есть о том, что мы еще не знаемфизику настолько, чтобы (даже в принципе) иметь возможность адекватно использовать ее язык для описания работы человеческого мозга. Но прежде мне потребуется дать хотя бы в общих чертах представление о достижениях и состоянии современной физической теории. В этой главе речь пойдет главным образом о той области, которую принято называть «классической физикой» и которая включает в себя механику Ньютона и теорию относительности Эйнштейна. По существу, термин «классическая» в данном случае означает, что обе теории достигли расцвета задолго до рождения (примерно в 1925 году, вдохновенными трудами таких физиков, как Планк, Эйнштейн, Бор, Гейзенберг, Шредингер, де Бройль, Борн, Иордан, Паули и Дирак) квантовой теории — загадочной теории, опирающейся на вероятности и индетерминизм и описывающей поведение молекул, атомов и субатомных частиц. В отличие от квантовой теории, классическая теория является детерминистской, поэтому будущее в ее рамках всегда полностью определяется прошлым. Но даже и в классической физике есть еще много загадок, несмотря на то, что знания, накопленные за несколько веков, позволили нам построить феноменально точную картину мира. Мы также должны будем рассмотреть и квантовую теорию (в главе 6), ибо я убежден, что — несмотря на мнение, разделяемое большинством физиологов — квантовые явления могутиграть важную роль в функционировании головного мозга человека. Но к этой теме мы обратимся в последующих главах.
К сегодняшнему дню наука достигла поразительных успехов. Достаточно бросить хотя бы беглый взгляд вокруг, чтобы воочию убедиться в невероятном могуществе, которое мы обрели благодаря нашему пониманию законов природы. Конечно, при создании современных технологий существенно использовались обширнейшие эмпирические данные. Однако куда более важна физическая теория, лежащая в основе этих технологий, и сейчас нас будет интересовать именно она. Теории, существующие в настоящее время, отличаются удивительной точностью. Но сила их заключается не только в способности правильно описывать соответствующие явления и процессы. Не меньшее значение имеет и то, что они, как оказывается, прекрасно поддаются точному и скрупулезному математическому анализу. Взятые вместе, эти обстоятельства позволили нам создать науку, обладающую поистине впечатляющей силой.