Энрике Грасиан: Мир математики. т.3. Простые числа. Долгая дорога к бесконечности

Тем не менее, именно компьютеры смогли делать вычисления, выходящие за пределы возможностей человеческого мозга. Машины могли даже имитировать дедуктивные рассуждения — одно из свойств математического мышления. В этот момент некоторые ученые почувствовали, что компьютеры достигли рубежа, к которому до сих пор ни одна машина не подходила. Был ли это правильный путь?

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

Противники компьютерных доказательств приводят два основных аргумента.

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

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

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

Подсчитано, что у суперкомпьютера Crayна каждую тысячу часов работы приходится лишь одна ошибка.

«Традиционные» математические подходы тоже никогда не были свободны от ошибок. В ряде случаев неверные результаты считались правильными в течение многих

лет. Кроме того, в наши дни математика достигла такого высокого уровня разнообразия и сложности, что проверка доказательства теоремы может занять годы, или доказательство будет понятно в лучшем случае лишь нескольким специалистам.

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

Когда говорят о полиномиальном времени, имеют в виду время, необходимое компьютеру для выполнения некоего алгоритма. Предположим, что у нас есть входная переменная п. Если алгоритм использует полиномиальные выражения, например, n 3+ 2n + 1, его называют полиномиальным алгоритмом (алгоритмом класса сложности Р). Если же выражение экспоненциальное, то говорят о неполиномиальном алгоритме (алгоритме класса сложности NP). В общих чертах идея состоит в том, что полиномиальные алгоритмы имеют приемлемое время работы, в отличие от неполиномиальных.

* * *

МАКСИМАЛЬНАЯ БЕЗОПАСНОСТЬ

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

* * *

Некоторые вычислительные задачи не могут быть решены с помощью детерминированного подхода — другими словами, с помощью процессов, выдающих уникальный и предполагаемый результат. Именно такими являются полиномиальные алгоритмы, работающие за полиномиальное время и выполняющие, например, операции сложения, умножения или решения систем уравнений. В большинстве случаев при использовании подходящих алгоритмов решение может быть найдено за разумное время. Задачи, которые могут быть решены таким образом, называются задачами класса сложности Р. С другой стороны, задачи класса сложности NP, для которых используются недетерминированные алгоритмы, решаются несколькими разными способами без гарантии получения одинакового результата.