Книга Эта странная математика. На краю бесконечности и за ним - Дэвид Дарлинг

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

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

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

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