Жар холодных числ и пафос бесстрастной логики

Наконец, рассмотрим еще один подход к понятию вычислимости, разработанный А. А. Марковым. Ведущий отечественный «математический конструктивиста поставил перед собой вопрос: к каким элементарным и математически точно определимым операциям можно было бы свести все процедуры, широко применяющиеся в математике и других науках и носящие название процессов, задаваемых алгоритмами? Известно, что математика прямо-таки изобилует алгоритмами — четкими предписаниями о подлежащих выполнению действиях. Но задача состояла в нахождении общего определения алгоритма (алгорифма) — определения, под которое подпадали бы не только все известные алгоритмы, но и те, которые появятся в будущем. Искомое точное определение алгоритма должно было соответствовать содержательно-интуитивному пониманию алгоритмов в математике: алгоритм — это «точное предписание, определяющее вычислительный процесс, ведущий от варьируемых исходных данных к искомому результату»[12]. Для построения такого определения необходимо было найти «атомы», из которых можно сформировать любое предписание — общепонятное, ясное, однозначно понимаемое. Задача эта была очень важна. Вот как раскрывает ее особую роль известный отечественный специалист по философским проблемам математики С. А. Яновская (1896—1966).

«Начиная с глубокой древности математики строили алгоритмы ... для решения целых классов задач определенного рода. Таковы, например: всем известный алгоритм Эвклида, представляющий собой программу действий, которые нужно выполнить, чтобы, имея любые два целых числа a и b, отыскать их общий наибольший делитель; алгоритм Штурма, позволяющий по заданию коэффициентов многочлена отделить его корни; многие другие алгоритмы алгебры, теории чисел, дифференциальных уравнений и многие, многие другие.

Когда какой-нибудь алгоритм отыскан, то всем ясно что он уже есть: его существование не приходится доказывать.

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

Для этого нужно знать, что, собственно, ищут; нужно иметь четкое определение алгоритма, позволяющее оперировать с этим понятием, как с математическим объектом»[13].

Значимость этой задачи для математики явственно видна на следующем важном примере. Среди двадцати трех проблем, поставленных Гильбертом в докладе «Математические проблемы» на Втором Международном конгрессе математиков в Париже (август 1900 г.), были и такие, которые впоследствии получили отрицательное решение. В частности, такой была десятая по номеру проблема. Приводим ее в формулировке самого Гильберта:

«10. Задача о разрешимости диофантова уравнения.

Пусть задано диофантово уравнение[14] с произвольными неизвестными и целыми рациональными числовыми коэффициентами. Указать способ, при помощи которого возможно после конечного числа операций установить, разрешимо ли это уравнение в целых рациональных числах»[15].

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

«Оглядываясь на пройденный путь, математики должны быть благодарны десятой проблеме Гильберта уже за то, что она послужила одним из стимулов для создания этой теории»[16]. Решение этой проблемы — решение отрицательное, доказывающее невозможность соответствующего алгоритма, было получено постепенно, усилиями ряда математиков; завершающий результат принадлежит представителю «четвертого поколения» марковской школы Ю. В. Матиясевичу, добившемуся успеха через 70 лет после постановки проблемы Гильбертом[17].

«Ясное и однозначно понимаемое предписание о действиях» может быть дано самыми разными путями: сформулировано на естественном языке (с выбором таких слов и выражений, которые не допускают разночтений), указано математическим соотношением, определено чертежом, номограммой, таблицей, графиком; иногда достаточно просто привести пример осуществления «способа», как его сущность становится ясной. Как же построить уточнение понятия о такого рода способах?