Параллельность, непрерывность и квантовые компьютеры

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

Действительно, в современных цифровых компьютерах общего назначения вычислениями занимается только процессор с ограниченным набором регистров и весьма небольшим кэшем. Как и в машине Тьюринга, имеется указатель на текущую инструкцию, которая и выполняется. В грубом приближении можно сказать, что используется лишь один вычислительный элемент (имеющий, правда, уже весьма сложную внутреннюю организацию), через который последовательно пропускаются команды. Это обеспечивает однозначность выполнения и простоту представления алгоритмов. Сейчас процессоры стали развиваться по пути увеличения числа отдельных «вычислителей» — ядер, но их количество остается незначительным. Память компьютера состоит из огромного числа элементов, которые, однако, не выполняют операций по преобразованию информации.

Такая организация вычислений разительно отличается от организации человеческого мозга, в котором каждый нейрон является отдельным вычислителем, работающим параллельно с другими. Можно представить мощность компьютера, у которого каждая ячейка памяти не просто хранит какую-то информацию, но и способна ее самостоятельно обрабатывать, обращаясь к информации в других ячейках! Может, мощность человеческого мышления кроется в параллельной обработке информации? Но ведь по грубым оценкам человеческий мозг способен выполнять порядка 1014 операций в секунду (поскольку он состоит из 1011 нейронов, каждый из которых передает до 1000 импульсов в секунду), что сопоставимо с мощностью современных компьютеров. Существуют, правда, гипотезы, что вычислительная мощность мозга гораздо больше благодаря сложным процессам, идущим внутри самих нейронов (одноклеточные организмы обладают сложным поведением, которое обеспечивается внутренней системой управления). Однако в мозге во многих группах нейронов одновременно активируется малый процент нейронов, и это отражается в том, что на уровне сознания мышление человека достаточно последовательное.

В настоящее время существуют и цифровые компьютеры, реализующие массовые параллельные вычисления. Это программируемые логические интегральные схемы (типа FPGA — Field-Programmable Gate Array), состоящие из большого числа логических блоков, между которыми могут устанавливаться различные связи. Хотя сами блоки являются сравнительно маломощными, благодаря их параллельной работе общая производительность может оказаться выше, чем у обычных процессоров. Очень популярными сейчас становятся вычисления на графических процессорах общего назначения (GPGPU), которые могут быть в десятки и сотни раз эффективнее вычислений на CPU. Однако множество задач, для которых удается добиться заметного выигрыша, ограничено. Наиболее типичными приложениями, для которых использование таких схем является оправданным, являются задачи по обработке изображений (и других сигналов), где каждая точка изображения может обрабатываться одной и той же процедурой параллельно, а также аппаратная реализация искусственных нейронных сетей некоторых типов.

Хотя на практике системы с массовой параллельностью могут быть полезны, в целом они пока не дают принципиального выигрыша и не решают проблему NP-полноты. Чтобы такое решение возникало, необходимо, чтобы число элементов в системе росло экспоненциально с ростом размерности задачи. Даже миллиард процессоров, работающих параллельно над одной NP-полной задачей, легко «поставить в тупик», лишь немного увеличив ее размерность (например, если мы таблицу, приведенную в предыдущем разделе, расширим столбцом N = 150, то у миллиарда параллельно работающих гигагерцевых процессоров уйдет 10,5 часов на ее решение…, а при N = 300 время решения будет намного превышать возраст Вселенной).

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

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

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

Хотя сейчас существуют интересные аналоговые решения, например в области оптических вычислений, эффект от их использования сродни эффекту от дискретных систем с массовым параллелизмом. Даже вопрос о дискретности самих физических процессов не до конца ясен. С одной стороны, почти все физические поля квантуются, т. е., истинно непрерывные вычисления, возможно, физически не реализуемы. С другой стороны, элементарные частицы представляются непрерывными волновыми функциями. Квантовый мир имеет и другие интересные свойства.

Несомненный интерес представляет преодоление проклятия размерности посредством «честного» воплощения недетерминированной машины Тьюринга в форме так называемых квантовых компьютеров, основа которых была заложена Ричардом Фейманом и Дэвидом Дойчем в 1980-х годах с использованием более ранних результатов других ученых.

Основной структурной единицей квантовых компьютеров является кубит — квантово-механическая система (например, отдельный атом), которая может находиться в одном из двух состояний. На первый взгляд, кубит выглядит как обычный классический бит памяти. Однако каждый кубит является активным элементом — он «эволюционирует» в соответствии с законами квантовой механики, переходя в другое состояние, что можно представить как вычисление. Квантовый компьютер может состоять из многих кубитов, эволюция каждого из которых будет зависеть от состояния прочих кубитов.

Казалось бы, такая совокупность кубитов представляет собой просто систему с массовой параллельностью. Но привлекательность квантовых компьютеров вовсе не в том, что они могут состоять из очень большого числа параллельно работающих элементов (это как раз обеспечить крайне сложно), а в том, что квантово-механическая система, по современным представлениям, обладает совершенно изумительным свойством — она может находиться в нескольких состояниях одновременно. Это именно то свойство, какое требуется от недетерминированной машины Тьюринга.

Но что это означает? Если классическая система из трех бит может находиться лишь в восьми состояниях: 000, 001, 010, …, 111, то квантово-механическая система может находиться не только в этих восьми чистых состояниях, но также и в любых смешанных состояниях вида 001 + 100 или 000 101++001 , т. е. в их суперпозиции (здесь используются классические обозначения состояний в квантовой механике, но опущены нормировочные коэффициенты). При этом состояния разных кубитов могут быть «зацепленными» (или «спутанными»), т. е. не просто каждый кубит по отдельности (независимо от других) находится в состояниях 0 и 1, но вся система находится сразу в состояниях (для последнего примера) 000 , и 101 001 . Эволюция каждого состояния соответствует вычислениям над собственным набором данных, и эти вычисления выполняются параллельно.

Многие воздействия на квантово-механическую систему переводят ее из одного состояния в несколько состояний, существующих одновременно. Например, единичный фотон при отражении от полупрозрачного стекла одновременно отразится от него и полетит насквозь, т. е. будет находиться сразу в обоих состояниях. И лишь при его регистрации произойдет таинственная редукция, в результате которой будет случайно выбрано одно из двух состояний.

Таким образом, квантовый компьютер действительно может быть истинным воплощением недетерминированной машины Тьюринга. Уже придуманы квантовые компьютеры, которые могут за полиномиальное время решать некоторые задачи, не относящиеся к классу Р, например задачу о разделении числа на простые сомножители. Несмотря даже на то, что каждый такой компьютер предназначен для реализации одного алгоритма (хотя сейчас предлагают и перепрограммируемые компьютеры), этот результат производит весьма сильное впечатление — настолько неожиданным был приход из физики решения некоторых проблем информатики. Действительно ли квантовые компьютеры могут решить проблему NP-полноты?

Пока ответить на этот вопрос сложно. Не все ученые даже согласны с тем, что квантово-механические системы действительно находятся в нескольких состояниях одновременно. Возможно, это лишь удобное математическое представление, а реальная система находится в одном состоянии, выбираемом как-то случайно (с точки зрения измерения состояния квантово-механической системы все именно так и выглядит). Хотя существуют эксперименты, свидетельствующие в пользу реальности квантовой суперпозиции, их интерпретация может оказаться и иной. Да и на хорошо известный парадокс кота Шрёдингера до сих пор нет единого ответа. Этот парадокс представляет собой мысленный эксперимент: поместим в закрытую коробку кота и механизм, который при детектировании распада ядра радиоактивного элемента (также находящегося в коробке) убивает кота. Пусть вероятность распада ядра в течение часа — 50 %, точнее, через час ядро будет находиться в суперпозиции двух равновероятных состояний — распавшемся и не распавшемся. Если эти состояния существуют одновременно, то и кот будет одновременно и живым, и мертвым. Но если коробку открыть, можно будет увидеть лишь одно состояние кота. Возникает вопрос: когда именно вместо двух состояний появляется одно? Существуют разные мнения: и то, что нахождение даже атома в нескольких состояниях одновременно — абстракция, и то, что редукция суперпозиции происходит при наблюдении или измерении (хотя понятие наблюдения остается смутным), и то, что при открытии коробки наблюдатель сам переходит в суперпозицию существующих одновременно, но никак не взаимодействующих состояний, в одном из которых он видит мертвого кота, а в другом — живого (по сути, вся Вселенная трактуется как множество таких параллельных разветвляющихся миров). Интересна интерпретация Пенроуза, согласно которой редукция суперпозиции тем вероятнее, чем больше разница энергий альтернативных состояний (что гораздо яснее идеи наблюдения). Окончательно реальность квантовой суперпозиции станет ясна лишь после создания настоящих квантовых компьютеров. Современные квантовые компьютеры не эквивалентны недетерминированным машинам Тьюринга.

Кроме того, даже если все теоретические предположения верны, может оказаться так, что на практике реализуемы лишь очень простые квантовые компьютеры, поскольку большие квантово-механические системы будет не только проблематично построить, но и крайне сложно оградить от возмущения со стороны окружения, нарушающего их работу.

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

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

Существование невычислимых физических процессов является красивой научной гипотезой. Представить саму возможность таких законов не так сложно: достаточно допустить, что, например, квантово-механическое состояние элементарной частицы изменяется не случайно, а в соответствии с решением некоторой алгоритмически неразрешимой задачи (например, диофантова уравнения, параметры которого определяются окружением). Еще совершенно не ясно, какие физические механизмы могут давать это решение (вера в их существование берется лишь из кажущейся неалгоритмичности человеческого разума). Пока некоторые физики ищут возможность обойти алгоритмичность, другим ученым остается работать в рамках классической алгоритмической парадигмы. Ведь даже если согласиться с утверждением Пенроуза о важности для мышления каких-то тонких физических процессов внутри клеток, никто не отменит тот простой факт, что человеческий мозг отличается от нервной системы, скажем, гидры, не протекающими в нем физическими процессами, а своей структурой, поддающейся алгоритмическому описанию. Кроме того, как уже отмечалось, проблема останова будет неразрешимой и для класса «неалгоритмических устройств».

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

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