справа вверху – “мигалка”, простейший из осцилляторов, которые после нескольких поколений возвращаются в исходную конфигурацию. В случае с “мигалкой” вертикальная ориентация чередуется с горизонтальной. Фигура справа внизу – “планер”.
“Планер”, через четыре поколения передвигающийся на одну клетку по диагонали.
Логический вентиль – это электронный компонент, преобразующий один или более входных сигналов в выходной сигнал. В принципе, компьютер можно создать, используя всего один тип логического вентиля, но, если взять три, задача существенно упростится. Речь о вентилях НЕ, И и ИЛИ. Вентиль НЕ выдает на выходе сигнал высокого уровня тогда и только тогда, когда получает на входе сигнал низкого уровня. Вентиль И выдает на выходе сигнал высокого уровня тогда и только тогда, когда оба входных сигнала – высокого уровня. Наконец, вентиль ИЛИ выдает сигнал высокого уровня тогда и только тогда, когда хотя бы один из входных сигналов – высокого уровня. Вентили можно объединять в схемы, способные и обрабатывать, и хранить данные.
Бесконечная схема из логических вентилей может моделировать работу машины Тьюринга. В свою очередь, работу логических вентилей можно моделировать с помощью игры “Жизнь”, а именно – используя различные сочетания ружей Госпера. Поток планеров из одного ружья будет выступать в качестве сигнала высокого уровня (“1”), а отсутствие планеров – сигнала низкого уровня (“0”). Что очень важно, планеры способны блокировать друг друга: сталкиваясь определенным образом, они взаимоуничтожаются. И наконец, венчает систему “пожиратель” – незамысловатая фигура из семи черных клеток. “Пожиратель” способен “поглощать” лишние планеры, не позволяя им нарушать другие компоненты системы, при этом сам он остается неизменным. Комбинируя разными способами “ружья Госпера” и “пожирателей”, мы можем моделировать различные логические вентили, а уже из них собрать действующую модель машины Тьюринга. Это кажется невероятным, но абсолютно все, на что способен самый мощный на свете суперкомпьютер, возможно сделать и с помощью игры “Жизнь” – только времени потребуется побольше. И точно так же, как в машине Тьюринга, в игре “Жизнь” невозможно написать программу, которая предсказала бы, чем закончится эволюция любого произвольного сочетания клеток, – ведь это противоречило бы выводу о неразрешимости проблемы остановки. Игра “Жизнь”, как и сама жизнь, непредсказуема и полна сюрпризов.
Современная теория алгоритмов опирается на идеи Тьюринга, однако она включает и еще одну концепцию, оставшуюся за рамками его исследований. В знаменитой статье 1936 года речь шла только о существовании алгоритмов, но не об их эффективности. Но на практике всех нас, конечно, интересуют алгоритмы скоростные, позволяющие компьютеру решать задачи как можно быстрее. Два алгоритма могут быть эквивалентны, то есть одинаково способны решить одну и ту же задачу, но, если один делает это за секунду, а другому требуется миллион лет, мы, естественно, выберем первый. Проблема с оценкой скорости алгоритма в том, что она зависит от многих факторов, как программных, так и аппаратных. Например, скорость выполнения одного и того же набора команд может различаться при использовании разных языков программирования. Чтобы представить в числовом выражении зависимость скорости алгоритма от количества входной информации (n), специалисты по вычислительным системам обычно пользуются обозначением “O большое” (от немецкого Ordnung – “порядок”). Если алгоритм программы имеет порядок n, то есть выполняется за время O(n), это означает, что время, необходимое для выполнения программы, приблизительно пропорционально размеру входных данных. Это справедливо, например, при сложении двух чисел в десятичной системе счисления. А вот на умножение нужно уже больше времени – O(n2).
Если говорят, что программа выполняется за так называемое полиномиальное время, это значит, что время ее выполнения не превышает размера входных данных, возведенного в определенную степень. Считается, что для большинства практических целей такой скорости обычно достаточно. Конечно, если степень выражается огромным числом, скажем, 100, то времени на выполнение программы понадобится очень уж много, но такое почти никогда не случается. Пример алгоритма с довольно высоким показателем степени – это алгоритм Агравала – Каяла – Саксены (АКС), который используют, чтобы проверить, является ли число простым. Он выполняется за время O(n12), поэтому на практике для проверки большинства чисел используют другой алгоритм, который выполняется хоть и не за полиномиальное время, но все же быстрее, чем АКС. А вот для поиска новых, очень больших, простых чисел алгоритм АКС незаменим.
Предположим, мы решили самым незамысловатым способом проверить, является ли простым некое число, состоящее из n знаков. Для этого нам нужно перебрать все числа от 2 до квадратного корня из нашего числа, определяя, не являются ли они его делителями. Можно немного облегчить себе работу, скажем, пропускать четные числа, но все равно времени на такую проверку понадобится O(√10n), или приблизительно O(3n). Такое время называется экспоненциальным – и благодаря компьютеру оно не выходит за разумные рамки, если n не слишком велико. Чтобы этим способом проверить на простоту одноразрядное число, потребуется три операции, которые суперкомпьютер, работающий со скоростью 1 квадриллион операций в секунду, выполнит за 3 фемтосекунды (3 квадриллионных части секунды). На проверку десятизначного числа понадобится уже около 60 пикосекунд, а двадцатизначного – примерно 3,5 микросекунды. Но, поскольку речь идет об экспоненциальном времени, по мере увеличения количества знаков в числе даже суперкомпьютер начинает захлебываться. Чтобы нашим примитивным методом проверить на простоту семидесятизначное число, потребуется уже около 2,5 квинтиллиона секунд – больше, чем нынешний возраст Вселенной. В подобных ситуациях не обойтись без быстрых алгоритмов.
Алгоритму вроде АКС, при условии что время выполнения операций выражается размером входных данных, возведенным в двенадцатую степень, на проверку простоты семидесятизначного числа потребуется “всего лишь” 14 миллионов секунд, или 160 дней. Это, конечно, все равно очень долго для скоростного компьютера, но по сравнению с астрономическим сроком, которого требует экспоненциальный алгоритм, почти молниеносно. Полиномиальные алгоритмы не всегда удобны на практике, но экспоненциальные при большом размере входных данных абсолютно неприемлемы. К счастью, есть целый ряд алгоритмов, занимающих промежуточное положение, и зачастую алгоритмы, которые работают “почти полиномиальное” время, достаточно практичны.
У всех машин Тьюринга, о которых мы говорили до сих пор, есть общая черта. В их алгоритмах – списках команд, указывающих им, что делать, – для каждой ситуации предусматривается только одно действие. Такие машины Тьюринга называются детерминированными (ДМТ). Получив команду, они автоматически ее выполняют: они неспособны “выбирать” между двумя различными командами. Но возможно представить себе и другой тип машин – недетерминированные (НМТ). В них каждая комбинация входных данных и состояния головки чтения-записи допускает выполнение более чем одной команды. НМТ – всего лишь мысленный эксперимент, построить ее в реальности было бы невозможно. Программа НМТ, например, могла бы включать как команду “Если текущее состояние 19 и обозреваемая ячейка содержит символ «1», нужно заменить его на «0» и перейти на одну ячейку вправо”, так и команду “Если текущее состояние 19 и обозреваемая ячейка содержит символ «1», нужно оставить его без изменений и перейти на одну ячейку влево”. В этом случае внутреннее состояние машины и символ на ленте не предусматривают единственно возможного действия. Вопрос: как же машина определяет, какое действие нужно выполнить?
НМТ изучает все возможные варианты решения задачи, а затем выбирает из них правильный (если он есть). Можно, конечно, считать такую машину просто исключительно везучим игроком, которому из множества решений всегда удается выбрать правильное. Но разумнее думать об НМТ как об устройстве, вычислительные способности которого возрастают по мере выполнения задачи таким образом, что каждый последующий шаг вычислений занимает не больше времени, чем предыдущий. Допустим, нужно выполнить поиск по двоичному дереву – структуре, в которой данные организованы таким образом, что в каждой точке (узле) происходит расщепление на два или более вариантов. Предположим, наша задача – найти в дереве конкретное число, скажем, 358. Машине нужно проходить каждый из всех возможных маршрутов до тех пор, пока она не найдет нужное число. Обычная машина Тьюринга, ДМТ, будет проходить их последовательно, один за другим, пока не наткнется на искомое значение. Поскольку количество ветвей в дереве увеличивается экспоненциально, удваиваясь на каждом уровне, на поиск нужного узла потребуется безнадежно много времени, если только по счастливой случайности он не будет находиться на одной из ближайших ветвей. А вот с НМТ ситуация меняется радикально: на каждом уровне двоичного дерева производительность машины словно бы удваивается, поэтому поиск на каждом последующем уровне занимает ровно столько же времени, сколько и на предыдущем, сколько бы ни было в дереве узлов.
В принципе, при наличии достаточного времени ДМТ под силу любая задача, с которой может справиться НМТ. Загвоздка как раз в “достаточности” времени. Ту же самую задачу, которую ДМТ выполняет за экспоненциальное время, НМТ способна была бы выполнить за полиномиальное. Жаль все-таки, что в реальности такая машина невозможна. Зато этот воображаемый компьютер позволил нам вплотную подобраться к одной из важнейших нерешенных проблем теории алгоритмов и математики в целом – так называемой проблеме равенства классов P и NP. Премия в миллион долларов обещана Математическим институтом Клэя тому, кто первым сумеет предложить доказуемо корректное решение