|
«Начиная с глубокой древности математики строили алгоритмы ... для решения целых классов задач определенного рода. Таковы, например: всем известный алгоритм Эвклида, представляющий собой программу действий, которые нужно выполнить, чтобы, имея любые два целых числа a и b , отыскать их общий наибольший делитель; алгоритм Штурма, позволяющий по заданию коэффициентов многочлена отделить его корни; многие другие алгоритмы алгебры, теории чисел, дифференциальных уравнений и многие, многие другие. Когда какой‑нибудь алгоритм отыскан, то всем ясно что он уже есть: его существование не приходится доказывать. Но если алгоритм упорно ищут и не находят, то естественно возникает вопрос, возможен ли он вообще? Разве обязательно должен существовать единый прием, позволяющий механически решить (по одной и той же программе) любую из всего класса задач, отличающихся друг от друга значениями каких‑либо параметров? Но как доказать несуществование алгоритма, его принципиальную невозможность? Для этого нужно знать, что, собственно, ищут; нужно иметь четкое определение алгоритма, позволяющее оперировать с этим понятием, как с математическим объектом»[136]. Значимость этой задачи для математики явственно видна на следующем важном примере. Среди двадцати трех проблем, поставленных Гильбертом в докладе «Математические проблемы» на Втором Международном конгрессе математиков в Париже (август 1900 г.), были и такие, которые впоследствии получили отрицательное решение. В частности, такой была десятая по номеру проблема. Приводим ее в формулировке самого Гильберта: «10. Задача о разрешимости диофантова уравнения. Пусть задано диофантово уравнение[137] с произвольными неизвестными и целыми рациональными числовыми коэффициентами. Указать способ, при помощи которого возможно после конечного числа операций установить, разрешимо ли это уравнение в целых рациональных числах»[138]. Как мы видим из этого текста, эта проблема была поставлена Гильбертом на интуитивно‑содержательном уровне, поэтому для ее решения нужно было проделать огромный путь, развить целые теории, разработать новые математические понятия. Ф. П. Варпаховский и А. Н. Колмогоров, говоря о теории алгоритмов, замечают: «Оглядываясь на пройденный путь, математики должны быть благодарны десятой проблеме Гильберта уже за то, что она послужила одним из стимулов для создания этой теории»[139]. Решение этой проблемы – решение отрицательное, доказывающее невозможность соответствующего алгоритма, было получено постепенно, усилиями ряда математиков; завершающий результат принадлежит представителю «четвертого поколения» марковской школы Ю. В. Матиясевичу, добившемуся успеха через 70 лет после постановки проблемы Гильбертом[140]. — 102 —
|