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