Жар холодных числ и пафос бесстрастной логики - [55]
Когда какой-нибудь алгоритм отыскан, то всем ясно что он уже есть: его существование не приходится доказывать.
Но если алгоритм упорно ищут и не находят, то естественно возникает вопрос, возможен ли он вообще? Разве обязательно должен существовать единый прием, позволяющий механически решить (по одной и той же программе) любую из всего класса задач, отличающихся друг от друга значениями каких-либо параметров? Но как доказать несуществование алгоритма, его принципиальную невозможность?
Для этого нужно знать, что, собственно, ищут; нужно иметь четкое определение алгоритма, позволяющее оперировать с этим понятием, как с математическим объектом»[13].
Значимость этой задачи для математики явственно видна на следующем важном примере. Среди двадцати трех проблем, поставленных Гильбертом в докладе «Математические проблемы» на Втором Международном конгрессе математиков в Париже (август 1900 г.), были и такие, которые впоследствии получили отрицательное решение. В частности, такой была десятая по номеру проблема. Приводим ее в формулировке самого Гильберта:
«10. Задача о разрешимости диофантова уравнения.
Пусть задано диофантово уравнение[14] с произвольными неизвестными и целыми рациональными числовыми коэффициентами. Указать способ, при помощи которого возможно после конечного числа операций установить, разрешимо ли это уравнение в целых рациональных числах»[15].
Как мы видим из этого текста, эта проблема была поставлена Гильбертом на интуитивно-содержательном уровне, поэтому для ее решения нужно было проделать огромный путь, развить целые теории, разработать новые математические понятия. Ф. П. Варпаховский и А. Н. Колмогоров, говоря о теории алгоритмов, замечают:
«Оглядываясь на пройденный путь, математики должны быть благодарны десятой проблеме Гильберта уже за то, что она послужила одним из стимулов для создания этой теории»[16]. Решение этой проблемы — решение отрицательное, доказывающее невозможность соответствующего алгоритма, было получено постепенно, усилиями ряда математиков; завершающий результат принадлежит представителю «четвертого поколения» марковской школы Ю. В. Матиясевичу, добившемуся успеха через 70 лет после постановки проблемы Гильбертом[17].
«Ясное и однозначно понимаемое предписание о действиях» может быть дано самыми разными путями: сформулировано на естественном языке (с выбором таких слов и выражений, которые не допускают разночтений), указано математическим соотношением, определено чертежом, номограммой, таблицей, графиком; иногда достаточно просто привести пример осуществления «способа», как его сущность становится ясной. Как же построить уточнение понятия о такого рода способах?
В начале 50-х годов в работах А. А. Маркова (первые публикации которого по теории алгоритмов относятся ко второй половине 40-х годов) получила развитие та идея, что все математические алгоритмы можно свести к повторению одной элементарной операции, выполняемой в строгом соответствии с начертанным на бумаге предписанием, которое после очень простого объяснения на естественном языке или даже демонстрации нескольких примеров становится ясным каждому человеку и всеми людьми понимается одинаково. В 1951 году в «Трудах Математического института АН СССР» (т. XXXVIII) была помещена статья А. А. Маркова «Теория алгорифмов», излагающая новую концепцию, а в 1954 году вышла его большая монография[18]. Ныне она, как и работы Чёрча и Тьюринга, является классической.
Марковские алгоритмы, которым их автор дал название «нормальных алгорифмов», работают над словами в каких-либо алфавитах, перерабатывая их в (другие) слова. Алгорифм состоит из вертикального списка команд (их называют формулами подстановок), каждая из которых имеет вид либо P → •Q, либо Q → P где P и Q — слова в некотором алфавите, не содержащем знаков • и →. Рассмотрим прежде всего действие отдельной формулы подстановки. Пусть в алфавите А = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9, —, +, =} дано слово 12 — 11 = 1 и команда
1 → 2.
Чтобы применить эту команду к данному слову, нужно найти в слове, двигаясь слева направо, первое вхождение левой (до стрелки) части команды и заменить его на правую (после стрелки) часть команды. Ясно, что в результате этого получится слово
22—11=1.
Если мы данную команду применим к этому слову, то получим:
22—21=1.
Следующие применения дадут:
22—22=1,
22—22=2.
Пытаясь применить команду в пятый раз, мы обнаружим, что в слове нет уже «подслова», совпадающего с левой частью команды. Команда, таким образом, перестанет срабатывать, и процесс применения данной формулы подстановки оборвется.
По существу, мы рассмотрели пример нормального алгорифма—алгорифма, состоящего из единственной команды. Если бы команда была не одна, то пользование алгорифмом не стало бы сложнее: в случае, когда самая верхняя команда не срабатывает, надо переходить к следующей команде; если и она не сработает, к следующей, и т. д. После срабатывания некоторой команды происходит возврат к самой верхней команде и ее проверка на применимость к полученному только-что слову и т. д. Если в ходе этого процесса встретится команда, содержащая после стрелки точку, процесс останавливается и слово, полученное в результате применения этой команды (называемой заключительной), объявляется результатом работы алгорифма.
