Том 3. Простые числа. Долгая дорога к бесконечности - страница 42

* * *

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

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

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

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

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

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

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

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

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

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

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

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

* * *