Сложность и вычислимость в физических объектах

Сложность и вычислимость в физических объектах

Теория сложности является важной для наших рассуждений в этой книге не только потому, что она касается вопроса возможности алгоритмизации, но и потому, что она позволяет для заведомо алгоритмизуемых объектов решать вопрос о том, могут ли использоваться соответствующие алгоритмы на практике. В последующих главах я буду больше говорить о вычислимости, чем о теории сложности, поскольку я склонен думать (хотя, конечно, и не имея для этого достаточных оснований), что, в отличие от фундаментального вопроса вычислимости, положения теории сложности не настолькр значимы для феномена мышления. Более того, мне представляется, что теория сложности сегодня лишь слегка затрагивает вопросы практичности алгоритмов.

Однако, я могу кардинально ошибаться по поводу важности той роли, которую играет сложность. Как будет показано позднее (глава 9, «Квантовые компьютеры»), теория сложности для реальных физических объектов, вероятно, может существенно отличаться от теории, изложенной мной ранее. Чтобы с уверенностью констатировать эту возможную разницу, необходимо будет использовать некоторые волшебные свойства квантовой механики — мистической, но все же поразительно точной теории, описывающей поведение атомов и молекул, а также и другие явления, многие из которых представляют интерес и на макромасштабах. Мы познакомимся с этой теорией в главе 6. Согласно ряду, идей, предложенных Давидом Дойчем [1985], существует принципиальная возможность построить «квантовый компьютер», на котором за «полиномиальное» время могут быть решены некоторые задачи (или классы задач), не принадлежащих Р. Пока совершенно неясно, как на практике сконструировать такое физическое устройство, которое бы (надежно) функционировало по принципу «квантового компьютера» — и, более того, рассматриваемый до сих пор класс задач носил заведомо искусственный характер, — но теоретически понятно, что квантовое физическое устройство могло бы улучшить работу машины Тьюринга.

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

Чтобы рассматривать эти вопросы, нам надо будет отойти на время от математических абстракций и задаться целью выяснить в следующих главах, как же, в действительности, ведет себя окружающий нас мир!