home | login | register | DMCA | contacts | help | donate |      

A B C D E F G H I J K L M N O P Q R S T U V W X Y Z
А Б В Г Д Е Ж З И Й К Л М Н О П Р С Т У Ф Х Ц Ч Ш Щ Э Ю Я


my bookshelf | genres | recommend | rating of books | rating of authors | reviews | new | форум | collections | читалки | авторам | add



Глава 5. Фантастическая машина Тьюринга

Можно создать одну-единственную машину, которую можно использовать для вычисления любой вычислимой последовательности[18].

Алан Тьюринг

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

В 1928 году немецкий математик Давид Гильберт, известный своим обыкновением ставить перед коллегами вопросы, на которые не было готового ответа[19], сформулировал задачу, названную им Entscheidungsproblem, или “проблемой разрешимости”. В задаче спрашивалось: всегда ли можно найти поэтапную процедуру, позволяющую за конечный промежуток времени определить, является математическое утверждение истинным или ложным? Гильберт надеялся на положительный ответ, но не прошло и десяти лет, как эта надежда рухнула.

Первый удар нанесла статья, опубликованная в 1931 году логиком австрийского происхождения Куртом Гёделем (о его работе мы еще поговорим подробнее в последней главе), изучавшим аксиоматические системы – наборы аксиом, или правил, принимаемых за самоочевидную истину, из которых выводятся теоремы. Гёдель показал, что в любой логически непротиворечивой системе аксиом, которая достаточно велика, чтобы включать в себя все правила арифметики, существуют истинные утверждения, чью истинность невозможно доказать средствами самой этой системы. Вывод, получивший название теорем Гёделя о неполноте, означал, что всегда будут существовать математические истины, которые невозможно доказать. Открытие стало потрясением для многих ученых, но оно еще не ставило крест на вопросе разрешимости математических утверждений, или, другими словами, на возможности найти алгоритм (последовательность шагов), способный гарантированно определить, является ли утверждение доказуемым, а если является – истинно оно или ложно. Крест на этом вопросе будет поставлен несколько позже, во многом благодаря молодому англичанину Алану Тьюрингу, который помог вынести окончательный вердикт по Entscheidungsproblem.

В жизни Тьюринга смешались триумф и трагедия: триумф гения, одного из основателей теории вычислительных систем, приблизившего окончание Второй мировой войны, и трагедия человека, на себе испытавшего отношение общества той поры к гомосексуалам. В раннем возрасте у него открылся удивительный талант к математике и естественным наукам. Проявился он уже в Шерборнской школе в графстве Дорсет, которую Тьюринг начал посещать в 1926 году в возрасте тринадцати лет. В школе Тьюринг крепко сдружился с другим талантливым учеником, своим одноклассником Кристофером Моркомом. Внезапная смерть Моркома в 1930 году глубоко потрясла Тьюринга. Он целиком посвятил себя занятиям математикой, а из-за потери друга стал проявлять острый интерес к природе человеческого разума и возможности жизни духа после смерти тела, надеясь, что ответ на этот вопрос сможет дать квантовая механика.

Во время учебы в Кембридже Тьюринг прослушал курс логики, из которого он узнал об Entscheidungsproblem. Убежденный в неправоте Гильберта, он решил посвятить этой проблеме отдельную научную работу. Тьюринг считал, что алгоритм, позволяющий определить, возможно ли доказать конкретное математическое утверждение, существует не всегда. Для работы над проблемой разрешимости ему требовался способ реализации алгоритмов: некое идеализированное устройство, умеющее выполнить любой заданный ему логический набор команд. Таким устройством стала придуманная им воображаемая “a-машина” (где буква а означала “автоматическая”), которая вскоре получила название “машина Тьюринга”, – чистая абстракция, он даже не предполагал воплощать ее в реальности. Конструкция ее была нарочито примитивной, а работала бы такая машина мучительно медленно. Она изначально создавалась исключительно как упрощенная до предела математическая модель вычислительной машины.

Машина Тьюринга состоит из бесконечно длинной ленты, разделенной на ячейки, каждая из которых может быть пустой или содержать 1 либо 0, и головки чтения-записи. Головка считывает по одной ячейке за шаг и выполняет определенное действие в зависимости от содержимого ячейки, внутреннего состояния головки и текущей команды в ее протоколе или программе. Команда может иметь, например, следующий вид: “Если вы находитесь в состоянии 18 и обозреваемая ячейка содержит 0, то замените его на 1, передвиньте ленту на одну ячейку влево и переключитесь в состояние 25”.

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

Простой пример: прибавление к цепочке из n единиц еще одной, или, другими словами, превращение n в n + 1. Входные данные в этом случае – последовательность единиц и за ней пустая ячейка либо, если n = 0, просто пустая ячейка. Головке дается первая команда: перейти к первой непустой ячейке – или, если известно, что на ленте нет вообще никаких данных, начать с любой ячейки – и считать ее содержимое. В случае, если в ячейке стоит 1, дается команда оставить ее как есть и перейти на одну ячейку вправо, не переключаясь в другое состояние; если же ячейка пустая, дается команда записать в ней 1 и остановиться. Дописав к цепочке цифр единицу, головка может, в зависимости от полученной команды, либо остановиться, либо вернуться в исходную позицию – например, для того чтобы начать процесс заново и дописать к цепочке еще одну единицу. Как вариант, после размещения головки над последней в цепочке единицей может быть введено какое-либо иное состояние, после чего головка начнет выполнять новый набор команд.

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

Затем Тьюринг создал в своем воображении особый вид вычислительной машины, известный сегодня под названием “универсальная машина Тьюринга”. Теоретически она была способна выполнять любую программу. Лента ее разделена на две части: на одной закодирована программа, на другой содержатся входные данные. Головка чтения-записи универсальной машины Тьюринга может перемещаться между этими частями и выполнять над входными данными операции в соответствии с командами, записанными в программе. Устройство предельно просто: бесконечно длинная лента, на которой содержится как программа, которую следует выполнить, так и входные и выходные данные, плюс головка чтения-записи. Машина может выполнять всего шесть простых операций: считывание, запись, перемещение влево, вправо, изменение состояния и остановка. Но, несмотря на эту простоту, возможности универсальной машины Тьюринга поражают воображение.

У вас наверняка есть хотя бы один компьютер. Неважно, какая на нем операционная система – какая-нибудь из версий Windows, Mac или Android либо иная, скажем, Linux. Производители любят подчеркивать преимущества и особенности своих операционных систем, выгодно отличающие их от конкурентов. Но с точки зрения математики при наличии достаточной памяти и времени все эти различные системы абсолютно идентичны. Более того, все они – полные эквиваленты той самой универсальной машины Тьюринга. Пусть на первый взгляд она и кажется чересчур примитивной, да и по эффективности не ровня мощным машинам нашего времени, но вот по своим возможностям она ничем не хуже любого современного компьютера.

Изобретение универсальной машины Тьюринга привело к возникновению такого понятия, как эмуляция. Говорят, что один компьютер способен эмулировать некий другой, если он может выполнять программу (называемую эмулятором), которая фактически превращает его в этот другой компьютер. Например, компьютер, работающий под управлением операционной системы Mac OS, может выполнить программу, которая заставит его вести себя так, как если бы на нем была установлена система Windows, – правда, на это требуется много оперативной памяти, а обработка данных происходит медленно. Если подобная эмуляция возможна, два компьютера считаются математически эквивалентными.

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

По оригинальному описанию Тьюринга был даже сконструирован целый ряд реальных машин – в основном в качестве экспериментов по проектированию или для демонстрации работы простейших вычислительных устройств. Несколько машин было построено из деталей LEGO, в том числе одна – из конструктора LEGO Mindstorms NXT для создания программируемого робота. А вот рабочая модель, созданная изобретателем из штата Висконсин Майком Дэйви, напротив, “воплощает в себе классические эстетичность и функциональность описанной Тьюрингом машины” и сейчас находится в постоянной экспозиции Музея истории компьютеров в городе Маунтин-Вью (штат Калифорния).


Эта странная математика. На краю бесконечности и за ним

Модель машины Тьюринга, построенная Майком Дэйви в соответствии с оригинальной идеей Алана Тьюринга.


Как уже упоминалось, свое изящное устройство Тьюринг придумал специально для того, чтобы дать ответ на проблему разрешимости, сформулированную Гильбертом, что он и сделал в своей статье 1936 года, озаглавленной “О вычислимых числах применительно к Entscheidungsproblem”. Если ввести в универсальную машину Тьюринга произвольные входные данные, она может либо остановиться, либо продолжать работать бесконечно. Тьюринг задался вопросом: возможно ли определить, остановится она или нет? Можно, конечно, запустить ее на неопределенное время и посмотреть, что произойдет. Но если после долгого ожидания вы решите досрочно прекратить эксперимент, не дождавшись результата, то так и не узнаете, остановилась бы машина сразу после этого этапа, гораздо позже либо продолжала бы работать бесконечно. Разумеется, для конкретных случаев просчитать результат можно, как мы в силах выяснить, остановится ли когда-нибудь простая машина Тьюринга. Однако Тьюринг хотел знать, существует ли общий алгоритм, способный для любых входных данных определить, остановится машина или нет. Эта задача получила название “проблема остановки”, и Тьюринг доказал, что такого алгоритма не существует. Далее, в заключительной части своей статьи, он показал, что отсюда следует вывод о неразрешимости Entscheidungsproblem. А это значит, что мы можем быть абсолютно уверены: никакая самая совершенная компьютерная программа не сумеет – во всех случаях – определить, завершит ли когда-нибудь свою работу какая-либо иная программа.

За месяц до выхода исторической статьи Тьюринга американский ученый-логик Алонзо Чёрч, его научный руководитель, независимо опубликовал собственную статью, в которой делал тот же вывод, но для доказательства использовал совершенно другой метод – лямбда-исчисление. Так же как и машина Тьюринга, лямбда-исчисление представляет собой универсальную вычислительную модель, но скорее программную, а не аппаратную; она оперирует “комбинаторами” – функциями, которые применяются к другим функциям. И Чёрч, и Тьюринг, пользуясь каждый своим методом, пришли, в сущности, к одному и тому же результату, получившему название “тезис Чёрча – Тьюринга”. Суть его в том, что человек способен высчитать или оценить количественно (такую мелочь, как ограниченность ресурсов, мы при этом в расчет не берем) только то, что вычислимо с помощью машины Тьюринга или равнозначного ей устройства. “Вычислимость” означает, что машина Тьюринга, если подать ей на вход программу (в двоичном представлении), способна работать до тех пор, пока не остановится, дав на выходе ответ (в таком же двоичном представлении). Основной вывод, следующий из тезиса Чёрча – Тьюринга, заключается в том, что общего решения Entscheidungsproblem не существует.

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

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

Есть в математике и другие вещи и явления, которые на первый взгляд не имеют ничего общего с машинами Тьюринга, но на поверку оказываются их эквивалентами (эмулирующими их). Один из примеров – игра “Жизнь”, придуманная английским математиком Джоном Конвеем. Идея игры пришла ему в голову, когда он заинтересовался проблемой, которую в 1940-х годах исследовал венгерско-американский математик и один из основоположников компьютерной науки Джон фон Нейман: возможно ли выдумать гипотетическую машину, способную производить точные копии самой себя? Фон Нейман доказал, что это возможно, создав математическую модель такой машины, где использовались разбитая на прямоугольные клетки область и набор очень сложных правил. Конвей задался вопросом, нельзя ли доказать то же более простым способом, – и придумал игру “Жизнь”. В игре Конвея используется (теоретически) бесконечное поле, разбитое на квадратные клетки, каждая из которых может быть окрашена либо в черный, либо в белый цвет. Игра начинается с произвольного узора из черных клеток и развивается по двум правилам:

1. Черная клетка остается черной, если ровно 2 или 3 из восьми соседних клеток тоже черные.

2. Белая клетка превращается в черную, если ровно 3 соседние клетки – черные.

Вот и все. И хотя освоить игру “Жизнь” может даже ребенок, она обладает всеми теми же возможностями, что и универсальная машина Тьюринга – а стало быть, что и любой когда-либо созданный в истории человечества компьютер. Впервые удивительная игра Конвея была представлена широкой аудитории в колонке Мартина Гарднера “Математические игры” в октябрьском выпуске журнала Scientific American за 1970 год. Гарднер познакомил своих читателей с основными фигурами в игре: “блоком” – квадратом размером 2 x 2 клетки, который по правилам игры никогда не изменяется, и “мигалкой” – прямоугольником размером 1 x 3 клетки, ориентация которого чередуется между горизонтальной и вертикальной, а центр остается неподвижным. “Планер” представляет собой фигуру из пяти клеток, передвигающуюся по диагонали на одну клетку за каждые четыре хода.

Поначалу Конвей думал, что, как бы ни располагались клетки в начале игры, их бесконечное “размножение” невозможно – любая конфигурация в конце концов стабилизируется, превратится в осциллятор или просто исчезнет, “умрет”. В той статье Гарднера 1970 года объявлялось, что Конвей предлагает премию в 50 долларов первому, кто докажет или опровергнет эту гипотезу. Не прошло и нескольких недель, как приз получила группа из Массачусетского технологического института под руководством математика и программиста Билла Госпера, одного из основателей сообщества хакеров. Так называемое “ружье Госпера” циклически “выстреливает” нескончаемую череду планеров со скоростью одна штука за тридцать поколений. Помимо того, что это увлекательное зрелище, “ружье Госпера” представляет интерес и с точки зрения теории: оно играет важнейшую роль в построении компьютеров на основе игры “Жизнь”, поскольку испускаемые им планеры можно принять за аналог потока электронов в компьютере. В реальной жизни, правда, эти потоки надо как-то контролировать, чтобы компьютер мог выполнять свое предназначение – вычислять. Как раз эту функцию выполняет логический вентиль.


Эта странная математика. На краю бесконечности и за ним

Четыре распространенных конфигурации в игре “Жизнь”. Слева: “блок” (вверху) и “улей” (внизу). Обе эти фигуры – “натюрморты”, то есть они не меняются в ходе игры. Фигура справа вверху – “мигалка”, простейший из осцилляторов, которые после нескольких поколений возвращаются в исходную конфигурацию. В случае с “мигалкой” вертикальная ориентация чередуется с горизонтальной. Фигура справа внизу – “планер”.


Эта странная математика. На краю бесконечности и за ним

“Планер”, через четыре поколения передвигающийся на одну клетку по диагонали.


Логический вентиль – это электронный компонент, преобразующий один или более входных сигналов в выходной сигнал. В принципе, компьютер можно создать, используя всего один тип логического вентиля, но, если взять три, задача существенно упростится. Речь о вентилях НЕ, И и ИЛИ. Вентиль НЕ выдает на выходе сигнал высокого уровня тогда и только тогда, когда получает на входе сигнал низкого уровня. Вентиль И выдает на выходе сигнал высокого уровня тогда и только тогда, когда оба входных сигнала – высокого уровня. Наконец, вентиль ИЛИ выдает сигнал высокого уровня тогда и только тогда, когда хотя бы один из входных сигналов – высокого уровня. Вентили можно объединять в схемы, способные и обрабатывать, и хранить данные.

Бесконечная схема из логических вентилей может моделировать работу машины Тьюринга. В свою очередь, работу логических вентилей можно моделировать с помощью игры “Жизнь”, а именно – используя различные сочетания ружей Госпера. Поток планеров из одного ружья будет выступать в качестве сигнала высокого уровня (“1”), а отсутствие планеров – сигнала низкого уровня (“0”). Что очень важно, планеры способны блокировать друг друга: сталкиваясь определенным образом, они взаимоуничтожаются. И наконец, венчает систему “пожиратель” – незамысловатая фигура из семи черных клеток. “Пожиратель” способен “поглощать” лишние планеры, не позволяя им нарушать другие компоненты системы, при этом сам он остается неизменным. Комбинируя разными способами “ружья Госпера” и “пожирателей”, мы можем моделировать различные логические вентили, а уже из них собрать действующую модель машины Тьюринга. Это кажется невероятным, но абсолютно все, на что способен самый мощный на свете суперкомпьютер, возможно сделать и с помощью игры “Жизнь” – только времени потребуется побольше. И точно так же, как в машине Тьюринга, в игре “Жизнь” невозможно написать программу, которая предсказала бы, чем закончится эволюция любого произвольного сочетания клеток, – ведь это противоречило бы выводу о неразрешимости проблемы остановки. Игра “Жизнь”, как и сама жизнь, непредсказуема и полна сюрпризов.

Современная теория алгоритмов опирается на идеи Тьюринга, однако она включает и еще одну концепцию, оставшуюся за рамками его исследований. В знаменитой статье 1936 года речь шла только о существовании алгоритмов, но не об их эффективности. Но на практике всех нас, конечно, интересуют алгоритмы скоростные, позволяющие компьютеру решать задачи как можно быстрее. Два алгоритма могут быть эквивалентны, то есть одинаково способны решить одну и ту же задачу, но, если один делает это за секунду, а другому требуется миллион лет, мы, естественно, выберем первый. Проблема с оценкой скорости алгоритма в том, что она зависит от многих факторов, как программных, так и аппаратных. Например, скорость выполнения одного и того же набора команд может различаться при использовании разных языков программирования. Чтобы представить в числовом выражении зависимость скорости алгоритма от количества входной информации (n), специалисты по вычислительным системам обычно пользуются обозначением “O большое” (от немецкого Ordnung – “порядок”). Если алгоритм программы имеет порядок n, то есть выполняется за время O(n), это означает, что время, необходимое для выполнения программы, приблизительно пропорционально размеру входных данных. Это справедливо, например, при сложении двух чисел в десятичной системе счисления. А вот на умножение нужно уже больше времени – O(n2).

Если говорят, что программа выполняется за так называемое полиномиальное время, это значит, что время ее выполнения не превышает размера входных данных, возведенного в определенную степень. Считается, что для большинства практических целей такой скорости обычно достаточно. Конечно, если степень выражается огромным числом, скажем, 100, то времени на выполнение программы понадобится очень уж много, но такое почти никогда не случается. Пример алгоритма с довольно высоким показателем степени – это алгоритм Агравала – Каяла – Саксены (АКС), который используют, чтобы проверить, является ли число простым. Он выполняется за время O(n12), поэтому на практике для проверки большинства чисел используют другой алгоритм, который выполняется хоть и не за полиномиальное время, но все же быстрее, чем АКС. А вот для поиска новых, очень больших, простых чисел алгоритм АКС незаменим.

Предположим, мы решили самым незамысловатым способом проверить, является ли простым некое число, состоящее из n знаков. Для этого нам нужно перебрать все числа от 2 до квадратного корня из нашего числа, определяя, не являются ли они его делителями. Можно немного облегчить себе работу, скажем, пропускать четные числа, но все равно времени на такую проверку понадобится O(n), или приблизительно O(3n). Такое время называется экспоненциальным – и благодаря компьютеру оно не выходит за разумные рамки, если n не слишком велико. Чтобы этим способом проверить на простоту одноразрядное число, потребуется три операции, которые суперкомпьютер, работающий со скоростью 1 квадриллион операций в секунду, выполнит за 3 фемтосекунды (3 квадриллионных части секунды). На проверку десятизначного числа понадобится уже около 60 пикосекунд, а двадцатизначного – примерно 3,5 микросекунды. Но, поскольку речь идет об экспоненциальном времени, по мере увеличения количества знаков в числе даже суперкомпьютер начинает захлебываться. Чтобы нашим примитивным методом проверить на простоту семидесятизначное число, потребуется уже около 2,5 квинтиллиона секунд – больше, чем нынешний возраст Вселенной. В подобных ситуациях не обойтись без быстрых алгоритмов.

Алгоритму вроде АКС, при условии что время выполнения операций выражается размером входных данных, возведенным в двенадцатую степень, на проверку простоты семидесятизначного числа потребуется “всего лишь” 14 миллионов секунд, или 160 дней. Это, конечно, все равно очень долго для скоростного компьютера, но по сравнению с астрономическим сроком, которого требует экспоненциальный алгоритм, почти молниеносно. Полиномиальные алгоритмы не всегда удобны на практике, но экспоненциальные при большом размере входных данных абсолютно неприемлемы. К счастью, есть целый ряд алгоритмов, занимающих промежуточное положение, и зачастую алгоритмы, которые работают “почти полиномиальное” время, достаточно практичны.

У всех машин Тьюринга, о которых мы говорили до сих пор, есть общая черта. В их алгоритмах – списках команд, указывающих им, что делать, – для каждой ситуации предусматривается только одно действие. Такие машины Тьюринга называются детерминированными (ДМТ). Получив команду, они автоматически ее выполняют: они неспособны “выбирать” между двумя различными командами. Но возможно представить себе и другой тип машин – недетерминированные (НМТ). В них каждая комбинация входных данных и состояния головки чтения-записи допускает выполнение более чем одной команды. НМТ – всего лишь мысленный эксперимент, построить ее в реальности было бы невозможно. Программа НМТ, например, могла бы включать как команду “Если текущее состояние 19 и обозреваемая ячейка содержит символ «1», нужно заменить его на «0» и перейти на одну ячейку вправо”, так и команду “Если текущее состояние 19 и обозреваемая ячейка содержит символ «1», нужно оставить его без изменений и перейти на одну ячейку влево”. В этом случае внутреннее состояние машины и символ на ленте не предусматривают единственно возможного действия. Вопрос: как же машина определяет, какое действие нужно выполнить?

НМТ изучает все возможные варианты решения задачи, а затем выбирает из них правильный (если он есть). Можно, конечно, считать такую машину просто исключительно везучим игроком, которому из множества решений всегда удается выбрать правильное. Но разумнее думать об НМТ как об устройстве, вычислительные способности которого возрастают по мере выполнения задачи таким образом, что каждый последующий шаг вычислений занимает не больше времени, чем предыдущий. Допустим, нужно выполнить поиск по двоичному дереву – структуре, в которой данные организованы таким образом, что в каждой точке (узле) происходит расщепление на два или более вариантов. Предположим, наша задача – найти в дереве конкретное число, скажем, 358. Машине нужно проходить каждый из всех возможных маршрутов до тех пор, пока она не найдет нужное число. Обычная машина Тьюринга, ДМТ, будет проходить их последовательно, один за другим, пока не наткнется на искомое значение. Поскольку количество ветвей в дереве увеличивается экспоненциально, удваиваясь на каждом уровне, на поиск нужного узла потребуется безнадежно много времени, если только по счастливой случайности он не будет находиться на одной из ближайших ветвей. А вот с НМТ ситуация меняется радикально: на каждом уровне двоичного дерева производительность машины словно бы удваивается, поэтому поиск на каждом последующем уровне занимает ровно столько же времени, сколько и на предыдущем, сколько бы ни было в дереве узлов.

В принципе, при наличии достаточного времени ДМТ под силу любая задача, с которой может справиться НМТ. Загвоздка как раз в “достаточности” времени. Ту же самую задачу, которую ДМТ выполняет за экспоненциальное время, НМТ способна была бы выполнить за полиномиальное. Жаль все-таки, что в реальности такая машина невозможна. Зато этот воображаемый компьютер позволил нам вплотную подобраться к одной из важнейших нерешенных проблем теории алгоритмов и математики в целом – так называемой проблеме равенства классов P и NP. Премия в миллион долларов обещана Математическим институтом Клэя тому, кто первым сумеет предложить доказуемо корректное решение[20]. P и NP – названия, присвоенные двум множествам задач разного класса сложности. Задачи множества P (от англ. polynomial – “полиномиальный”) могут быть решены за полиномиальное время на обычной (детерминированной) машине Тьюринга. Задачи множества NP (от англ. non-deterministic polynomial – “недетерминированный полиномиальный”) – это те, которые мы могли бы решить за полиномиальное время, будь у нас НМТ. (Одна из таких задач – разложение больших чисел на простые сомножители. НМТ способна выполнить поиск нужного множителя в двоичном дереве быстро, за полиномиальное время, тогда как ДМТ придется прочесывать каждую ветвь, что займет экспоненциальное время.) Это означает, что все задачи множества P принадлежат также и множеству NP, поскольку НМТ может делать все то же, что и обычная машина Тьюринга, за то же время.

Разумно предположить, что множество NP больше, чем P, ведь оно включает и те задачи, которые можно решить только на машине Тьюринга, обладающей сверхспособностями – поразительной везучестью или фантастической производительностью. Но на сегодня никем пока не доказано, что обычная ДМТ не способна на все то же, что по силам НМТ, хотя такое предположение и кажется весьма правдоподобным. Однако для математиков есть огромная разница между разумным предположением и достоверностью. Пока нет убедительных свидетельств иного, всегда остается возможность, что кто-то докажет равенство множеств N и NP – почему, собственно, проблема и носит такое название. Миллион долларов – сумма немалая, но как ее получить, если для этого нужно доказать (или опровергнуть), что все задачи класса NP принадлежат также и классу P? Небольшой повод для оптимизма дает факт существования так называемых NP-полных задач. Они примечательны тем, что, если для решения хотя бы одной из них удастся найти полиномиальный алгоритм, выполняемый на обычной машине Тьюринга, это будет означать, что такой алгоритм существует для всех задач класса NP. В этом случае утверждение “P = NP” будет истинным.

Первая NP-полная задача, названная задачей выполнимости булевых формул, или SAT[21], была сформулирована в 1971 году американско-канадским математиком и специалистом в области теории вычислительных систем Стивеном Куком. Ее можно выразить в терминах логических вентилей. Имеется схема, состоящая из произвольного множества логических вентилей и входов (но не имеющая обратной связи) и ровно одного выхода. Вопрос: можно ли найти такое сочетание входов, при котором выход “включится”? В принципе, решение всегда можно искать перебором всех возможных сочетаний входов в системе, но это все равно что использовать экспоненциальный алгоритм. Чтобы доказать равенство P и NP, придется доказать, что есть более быстрый – полиномиальный – способ получить ответ.

SAT – хотя и первая, но не самая известная из NP-полных задач. Эта честь принадлежит задаче коммивояжера, уходящей корнями в середину XIX века. В руководстве для коммивояжеров, опубликованном в 1832 году, шла речь о наиболее эффективном способе объехать ряд городов в Германии и Швейцарии. Научную формулировку задаче впервые дали пару десятилетий спустя ирландский физик и математик Уильям Гамильтон и англиканский священник и математик Томас Киркман. Предположим, что коммивояжеру нужно объехать множество городов и ему известно расстояние (не обязательно по прямому маршруту) между каждой парой городов. Необходимо найти кратчайший маршрут, по которому можно объехать все города и вернуться в исходный. Только в 1972 году было доказано, что эта задача является NP-полной (то есть что построение полиномиального алгоритма для ее решения докажет равенство P и NP). Это объясняет, почему не одно поколение математиков, в последнее время даже вооруженных компьютерами, сталкивалось с трудностями при поиске оптимальных решений для сложных маршрутов.

Понять условия задачи коммивояжера не составит труда никому, а вот решить ее ничуть не проще, чем любую другую NP-полную задачу – все они чрезвычайно сложны. Математикам не дает покоя то, что построение полиномиального алгоритма для любой NP-полной задачи докажет, что P = NP. Последствия этого будут очень серьезны: в частности, это будет означать, что существует полиномиальный алгоритм для взлома RSA – метода криптографической защиты (мы еще поговорим о нем позже), на который мы полагаемся ежедневно, например, при получении банковских услуг. Хотя, скорее всего, такого алгоритма все же не существует.

Недетерминированные машины Тьюринга существуют, как мы уже выяснили, только в нашем воображении. Другое дело – квантовый компьютер, потенциально тоже чрезвычайно мощное устройство, которое уже начали создавать. Как ясно из названия, в основе принципа его работы лежит ряд очень странных явлений из области квантовой механики. А оперирует он не обычными битами (от англ. binary digit – “двоичное число”), а квантовыми, так называемыми кубитами (от англ. quantum bit – “квантовый бит”). Кубит, который может представлять собой просто электрон с неизвестным спином, имеет в контексте квантовых эффектов две характеристики, отсутствующие у обычного бита в традиционном компьютере. Во-первых, он может находиться в суперпозиции состояний: одновременно представлять собой и 0, и 1, а становиться тем или другим только тогда, когда за ним наблюдают. Это же явление можно истолковать и по-другому: квантовый компьютер, вместе со всей остальной вселенной, расщепляется на две копии самого себя, в одной из которых бит 1, а в другой – бит 0, и только при измерении кубита он, вместе с окружающей его вселенной, “схлопывается” в конкретное значение. Второе любопытное свойство, лежащее в основе работы квантовых компьютеров, – запутанность. Два запутанных кубита, даже будучи разделенными в пространстве, так связаны друг с другом явлением, которое окрестили “жутким дальнодействием”, что измерение одного из них мгновенно влияет на измерение второго.

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


Эта странная математика. На краю бесконечности и за ним

Профессор Уинфрид Хенсингер (слева) и Себастьян Вайдт работают над прототипом квантового компьютера.


Заманчиво приравнять квантовые компьютеры к недетерминированным машинам Тьюринга, но, увы, это разные вещи. Да, их вычислительные возможности одинаковы, в этом смысле недетерминированные машины Тьюринга не превосходят детерминированные: на ДМТ можно смоделировать как первые, так и вторые. А вот по эффективности квантовым компьютерам вряд ли удастся догнать НМТ, что неудивительно, поскольку НМТ – исключительно гипотетические устройства. Маловероятно, например (хоть это пока и не доказано), что они смогут решать NP-полные задачи за полиномиальное время. Впрочем, одну задачу, которую раньше считали не имеющей такого решения (что предполагало бы ложность равенства “P = NP”), все же удалось с помощью квантовых компьютеров решить за полиномиальное время – это разложение больших чисел на простые множители. В 1994 году американский математик Питер Шор разработал для этого квантовый алгоритм, учитывающий особые свойства такой задачи. К сожалению, аналогичный метод не может быть применен для решения других задач, например NP-полных. Если и можно разработать для квантовых компьютеров полиномиальный алгоритм решения NP-полной задачи, он опять-таки должен задействовать ее специфические особенности.

Как и любая другая молодая и перспективная технология, квантовые компьютеры – это и множество надежд, и немало проблем. Среди последних – вероятность взлома шифров, которые до сих пор считались высокозащищенными, в основном потому, что, несмотря на все предпринятые усилия, за последние несколько десятилетий никому не удалось разработать полиномиальный метод их дешифровки. Современные методы криптографической защиты основаны на алгоритме RSA, названном так по первым буквам фамилий его изобретателей Рона Ривеста, Ади Шамира и Леонарда Адлемана[22]. Алгоритм позволяет очень быстро зашифровать данные и используется ежедневно, ежесекундно при обмене данными в интернете. А вот расшифровка тем же алгоритмом без специальной информации – ключа – происходит гораздо медленнее и требует экспоненциального времени. Именно этой асимметрией скорости и необходимостью обладать дополнительной информацией объясняется эффективность RSA. Работает алгоритм следующим образом: у каждого пользователя есть два ключа – открытый и секретный. С помощью открытого, общедоступного ключа информация шифруется, а секретный ключ, предназначенный для расшифровки, известен только его владельцу. Отправить защищенное сообщение просто – достаточно с помощью открытого ключа применить алгоритм. Но прочитать сообщение сможет только его адресат, имеющий секретный ключ. Теоретически секретный ключ возможно разгадать, зная открытый, но для этого придется разлагать на множители огромные числа, состоящие из сотен знаков. Если ключи достаточно большие, то для расшифровки сообщений, которые мы постоянно отправляем при совершении банковских и других конфиденциальных операций, понадобится задействовать все компьютеры мира, причем работать им нужно будет гораздо больше времени, чем текущий возраст Вселенной. Есть, однако, опасения, что с приходом квантовых компьютеров ситуация может круто измениться.

В 2001 году с помощью алгоритма Шора, который позволяет осуществлять разложение чисел на множители за полиномиальное время, и 7-кубитного квантового компьютера число 15 было разложено на множители 3 и 5. Десятилетие спустя тем же методом было разложено число 21. Оба достижения кажутся смехотворно скромными, учитывая, что то же без труда сделает любой школьник, знающий таблицу умножения. Но вот в 2014 году с помощью другого алгоритма и квантовой вычислительной системы были разложены на простые множители уже гораздо более внушительные числа, 56 153 – самое большое[23]. Даже этот результат может показаться не очень впечатляющим на фоне проблемы разложения на множители гигантских чисел, состоящих из сотен знаков. Однако с ростом числа кубитов в квантовых компьютерах успешная дешифровка всех шифров RSA рано или поздно станет возможной. Когда это произойдет, сегодняшние способы обмена данными в интернете перестанут быть безопасными – и банковская индустрия, а вместе с ней и все другие системы, требующие защиты передаваемых данных, будут повергнуты в хаос. Вероятно, удастся разработать новую систему криптографической защиты на основе NP-трудных задач – таких, которые не менее трудны для решения, чем NP-полные, но не обязательно относятся к классу NP. Наиболее сложные из NP-полных задач решить очень непросто, но для более типичных случаев обычно можно подобрать подходящий алгоритм. Криптографическую защиту на основе таких задач будет довольно легко взломать, хотя небольшая вероятность того, что шифр окажется крайне сложным, все же есть. Для надежной защиты нужен алгоритм, почти всегда дающий крайне сложный шифр, требующий экспоненциального времени для взлома. Пока такой метод не разработан, хотя в принципе это возможно. Если квантовые компьютеры окажутся неспособными решать NP-полные (а значит, и NP-трудные) задачи, то разработка такого криптографического метода даст нам возможность снова почувствовать себя в безопасности, хотя бы на какое-то время.

Большинство ученых, занимающихся вычислительными системами, полагают, что P /= NP. Это мнение подкреплено десятилетиями исследований, в результате которых ни для одной из более чем 3000 известных NP-полных задач не было найдено ни единого алгоритма, позволяющего решить ее за полиномиальное время. И все же аргумент, основанный на отрицательном опыте, не слишком убедителен, особенно в свете неожиданного доказательства Великой теоремы Ферма – очень просто сформулированной задачи, для решения которой потребовались огромные усилия и самые передовые методы. Чисто философские аргументы в пользу того, что P /= NP, также не очень убедительны. Скотт Ааронсон, математик, специалист в области теории вычислительных систем, преподающий в Массачусетском технологическом институте, заявил: “Если окажется, что P = NP, то мир станет совершенно не таким, каким мы его обычно считаем. Не будет больше никакой особой ценности в «творческих скачках», исчезнет принципиальная разница между решением задачи и признанием правильности найденного решения”. Тем не менее и в математике, и в других науках с завидной частотой происходят события, полностью переворачивающие наши представления об окружающем мире. Если действительно окажется, что P = NP, то, прежде всего, вряд ли это открытие будет иметь большое практическое значение – ведь доказательство, скорее всего, будет неконструктивным. Другими словами, даже если будет доказано, что для решения NP-полных задач существуют полиномиальные алгоритмы, ни одного конкретного алгоритма в доказательстве приведено не будет. Так что по крайней мере в ближайшем будущем нашим защищенным данным ничто не угрожает – хотя не совсем ясно, как долго это продлится, ведь математики уже всерьез занялись поиском такого алгоритма.

В любом случае, прежде чем существенные сдвиги в решении проблемы равенства P и NP или в разработке более эффективных алгоритмов поставят под угрозу безопасность наших данных, на помощь нам, вероятно, подоспеет квантовая механика. Разработки в области квантовой криптографии могут привести к созданию абсолютно стойкого шифра, не поддающегося дешифровке никакими методами. Один из действительно нераскрываемых шифров был изобретен еще в 1886 году и получил название “одноразовый блокнот”. Ключ представляет собой случайную последовательность букв той же длины, что и сообщение. Сообщение объединяется с ключом путем присвоения каждой букве числового значения (A = 1, B = 2 и так далее), сложения числовых значений букв сообщения и соответствующих им букв ключа, вычитания из получившихся сумм 26, в случае если сумма превышает 26, и последующего обратного превращения чисел в буквы[24]. Доказано, что этот метод является абсолютно криптостойким. Даже если у кого-то найдется достаточно времени, чтобы перебрать все возможные комбинации, будет совершенно невозможно отличить правильную расшифровку от множества неправильных вариантов. Важное условие: чтобы шифр невозможно было взломать, ключ должен после использования уничтожаться. Если его использовать повторно, то любой человек, имеющий в своем распоряжении оба зашифрованных сообщения и знающий, что ключ один и тот же, сможет их расшифровать. Кроме того, ключи должны передаваться секретно, поскольку доступ к ключу грозит мгновенной расшифровкой. Одноразовые шифры в свое время использовались советскими шпионами. Они сшивались в крошечные блокноты и пропитывались специальным горючим составом, чтобы при уничтожении от них не оставалось и следа. Такие шифры и сейчас используются для защиты данных, передаваемых по линии прямой связи между президентами США и России. Но необходимость секретно обмениваться ключами – серьезный недостаток метода, делающий его непригодным для большинства практических целей, например для передачи данных онлайн.

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

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

Область квантовых вычислений развивается очень динамично. В 2017 году физики из Университета Сассекса обнародовали проект создания крупномасштабных квантовых компьютеров, сделав его доступным для всех. В этом проекте разъясняется, как избежать декогеренции – проблемы, которая до тех пор мешала ученым создать в лабораторных условиях устройство более чем на 10–15 кубитов. Также там приводится описание конкретных технологий, которые позволят сделать реальностью мощные квантовые компьютеры с гораздо большим числом кубитов. Среди таких технологий: использование в качестве кубитов ионов (заряженных атомов), захваченных в специальные ловушки, при комнатной температуре; передача ионов из одного модуля системы в другой при помощи электрических полей; а также применение логических вентилей, контролируемых микроволнами и изменением напряжения. Для начала ученые из Университета Сассекса собираются построить небольшой прототип квантового компьютера. Тем временем Google, Microsoft и множество различных стартапов, таких как IonQ, разрабатывают собственные схемы, основанные на захвате ионов в ловушки, использовании явления сверхпроводимости и (в случае с Microsoft) на концепции топологических квантовых вычислений. Компания IBM объявила о своих планах “через несколько лет” вывести на рынок квантовый компьютер на 50 кубитов, а ученые уже заглядывают дальше, предвидя то время, когда реальностью станут машины на миллионы, а то и на миллиарды кубитов[25].

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


Глава 4. Порядок на грани хаоса | Эта странная математика. На краю бесконечности и за ним | Глава 6. Музыка сфер