Эта странная математика

Бесконечная схема из логических вентилей может моделировать работу машины Тьюринга. В свою очередь, работу логических вентилей можно моделировать с помощью игры “Жизнь”, а именно – используя различные сочетания ружей Госпера. Поток планеров из одного ружья будет выступать в качестве сигнала высокого уровня (“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 квинтиллиона секунд – больше, чем нынешний возраст Вселенной. В подобных ситуациях не обойтись без быстрых алгоритмов.