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

В начале 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 году была опубликована теорема, доказанная учеником А. А. Маркова В. К. Детловсом, о том, что всякий процесс, осуществимый с помощью нормального алгорифма, осуществим также посредством некоторой рекурсивной функции.