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

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

В начале 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.

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

По существу, мы рассмотрели пример нормального алгорифма—алгорифма, состоящего из единственной команды. Если бы команда была не одна, то пользование алгорифмом не стало бы сложнее: в случае, когда самая верхняя команда не срабатывает, надо переходить к следующей команде; если и она не сработает, к следующей, и т. д. После срабатывания некоторой команды происходит возврат к самой верхней команде и ее проверка на применимость к полученному только-что слову и т. д. Если в ходе этого процесса встретится команда, содержащая после стрелки точку, процесс останавливается и слово, полученное в результате применения этой команды (называемой заключительной), объявляется результатом работы алгорифма.

Может случиться, что на каком-то такте работы алгорифма ни одна из формул подстановок (ни одна из команд) не окажется применимой. Тогда произойдет естественный обрыв процесса переработки слов, и слово, при этом полученное, считается результатом. Если же в процессе применения алгорифма к некоторому слову не происходит ни естественного обрыва процесса, ни применения заключительной формулы подстановки—то есть если процесс переработки исходного слова продолжается неограниченно долго, то считается, что алгорифм к этому слову не применим.

Описанные правила настолько элементарны, что мы предоставляем читателю самостоятельно проследить за действием алгорифма

1 → 2

2 → 3

3 → 444,

примененного к слову 12—11 = 1. Для контроля мы выпишем последовательность слов, получаемых после каждого применения подходящей команды, разделяя их точкой с запятой: 12—11 = 1 (исходное слово);

22—11=1; 22—21 = 1; 22 — 22 = 1; 22 — 22 = 2; 32 — 22 = 2;

33 —22 =2; 33 — 32 = 2; 33 — 33 = 2; 33 — 33 = 3; 4443 — 33 = 3;

444444 — 33 = 3; 444444 — 4443 = 3; 444444 — 444444 = 3;

444444 — 444444 = 444.

На последнем слове процесс оборвется, и оно окажется результатом. В этом случае говорят, что данный алгорифм переработал слово 12—11=1 в слово 444444 — 444444 = 444.

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

И действительно, как было доказано, с помощью нормальных алгорифмов можно «промоделировать» любой вычислительный процесс, реализуемый на тьюринговой машине. Отсюда и из доказанной в математической логике теоремы о возможности осуществления любого рекурсивного процесса на некоторой машине Тьюринга вытекает, что алгорифмы Маркова могут делать все то, что делают рекурсивные функции. Но не охватывают ли марковские алгорифмы более широкого круга процедур? Ведь алфавиты и списки формул подстановок могут быть исключительно разнообразными.

Вскоре после создания теории нормальных алгорифмов, в 1953 году была опубликована теорема, доказанная учеником А. А. Маркова В. К. Детловсом, о том, что всякий процесс, осуществимый с помощью нормального алгорифма, осуществим также посредством некоторой рекурсивной функции.

Это значит, что рекурсивные функции и машины Тьюринга «равнообъемны» нормальным алгорифмам и что тезисы Чёрча и Тьюринга получают подкрепление в виде принципа нормализации (это название предложено А. А. Марковым; можно условиться называть этот принцип и по-другому, например, тезисом Маркова): всякое точное общепонятное предписание, определяющее произвольный потенциально осуществимый процесс переработки слов в каком-либо алфавите, ведущий от варьируемых исходных данных к некоторому результату, эквивалентно некоторому нормальному алгорифму.

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

Как и Чёрч в статье 1936 года, А. А. Марков приводит в своей фундаментальной монографии «Теория алгорифмов» ряд аргументов в пользу принципа нормализации. Как и у Чёрча, это не доказательства, а только соображения, к которым можно отнести прилагательное «убедительные». Они апеллируют прежде всего к практике математики. Исследования Маркова, давшие ему возможность найти разумные основания для подкрепления его тезиса, следует считать важным этапом в становлении основной гипотезы теории алгоритмов (теории эффективной вычислимости) — гипотезы, общий смысл которой состоит в утверждении, что различные, оказавшиеся эквивалентными друг другу, уточнения идеи алгоритма и вычислимости — рекурсивные функции, тьюринговы машины, нормальные алгорифмы [19]— исчерпывающим образом описывают (каждое — в терминах своего специфического языка) эту идею.