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

В ходе своих новаторских исследований хаоса Лоренц также обнаружил новый вид фрактала, так называемый странный аттрактор. Обычный аттрактор прост в том смысле, что точки стремятся к нему, а затем совершают определенные постоянные циклы в его окрестностях. Странные же аттракторы, как мы увидим, ведут себя иначе. Для того чтобы получить первый пример странного аттрактора, Лоренц использовал систему дифференциальных уравнений. При увеличении масштаба в любой его точке появлялось бесконечное множество параллельных линий. Любая точка на аттракторе передвигалась по хаотической траектории рядом с ним, никогда не возвращаясь точно в исходное положение, а две точки, находившиеся изначально очень близко друг к другу, быстро расходились и в итоге оказывались на совершенно разных траекториях. Чтобы провести аналогию с физическим миром, представьте себе шарик для настольного тенниса и океан. Если шарик сбросить с высоты над океаном, он будет быстро падать, пока не коснется воды. Если его погрузить под воду и отпустить там, он быстро всплывет. Но как только он оказывается на поверхности океана, его движение становится совершенно непредсказуемым и хаотичным. Точно так же точка, не находящаяся на странном аттракторе, будет стремительно двигаться по направлению к нему. Достигнув же странного аттрактора, она начинает двигаться вблизи него хаотично.

Изучение фракталов – увлекательнейшее занятие, а по красоте мало какой математический объект способен составить им конкуренцию. Но кроме того, они играют важнейшую роль в физическом мире. В основе любого природного явления, которое кажется нам случайным и неупорядоченным, может лежать фрактал. Более того, можно даже утверждать, что все объекты и явления, существующие в этом мире, – фракталы, поскольку все они на любом уровне имеют ту или иную структуру, по крайней мере до уровня атомов. Облака, вены на руке, разветвления бронхов, листья деревьев – все они имеют структуру фрактала. В космологии по фрактальному принципу распределяется материя по Вселенной, и фрактал этот имеет структуру даже на уровнях меньше атомного ядра, вплоть до предельного значения расстояния, которому присвоен физический смысл, – так называемой планковской длины, равной 1,6 × 10^–35 метра, или приблизительно одной стоквинтиллионной размера протона.

Странный аттрактор, известный как “циклически симметричный аттрактор Томаса”.

Фракталы существуют не только как пространственные узоры, но и как временны́е. Возьмите игру на ударных: можно легко запрограммировать компьютер на создание и воспроизведение барабанной партии или посадить за ударную установку музыканта-робота. Но в игре профессиональных барабанщиков есть нечто, что отличает ее от идеально размеренного, безукоризненно точного ритма, производимого их электронными коллегами. И это “нечто” – незначительные изменения ритма и громкости, едва заметные отклонения от совершенства, которые, как показывают исследования, имеют фрактальный характер.

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

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

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

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

Можно создать одну-единственную машину, которую можно использовать для вычисления любой вычислимой последовательности[18]18
  Петцольд Ч. Читаем Тьюринга. М.: ДМК Пресс, 2016.


[Закрыть].

Алан Тьюринг

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

В 1928 году немецкий математик Давид Гильберт, известный своим обыкновением ставить перед коллегами вопросы, на которые не было готового ответа[19]19
  В 1900 году на II Международном конгрессе математиков в Париже Гильберт сформулировал 23 проблемы, которые считал важнейшими в математике. Эти задачи, называемые проблемами Гильберта, оказали существенное влияние на математику XX века. На настоящий момент полностью решены 12 из них (если не считать нескольких, в которых формулировка оказалась слишком расплывчатой для создания математического утверждения). – Прим. науч. ред.


[Закрыть], сформулировал задачу, названную им 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 × 2 клетки, который по правилам игры никогда не изменяется, и “мигалкой” – прямоугольником размером 1 × 3 клетки, ориентация которого чередуется между горизонтальной и вертикальной, а центр остается неподвижным. “Планер” представляет собой фигуру из пяти клеток, передвигающуюся по диагонали на одну клетку за каждые четыре хода.

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

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

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

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

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

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

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

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

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

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