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

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

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]— исчерпывающим образом описывают (каждое — в терминах своего специфического языка) эту идею.

Ситуацию с этой гипотезой можно сравнить с ситуацией, сложившейся в физике вокруг закона сохранения энергии. Как и всякий закон теоретической физики, доказать его так, как математики доказывают теоремы, невозможно. Но этот закон — положение, в пользу которого наука находит все новые аргументы, идущие с самых разных сторон. Развитие теории и организация все более точных экспериментов порождают дополнительные «соображения», обладающие свойством убедительности (если говорить о теоретических соображениях, то в последнее время это — большей частью «соображения симметрии», понимаемой в довольно широком смысле). Они ложатся дополнительным грузом на чашу весов нашего знания. Кроме того — и это самое существенное, вся человеческая практика, изменяющая мир, в частности вся современная промышленная технология, основывается в большой мере на фундаментальных законах физики, а следовательно, и на одном из наиболее важных утверждений физики — законе сохранения энергии.

Не так ли обстоит дело и в отношении основной гипотезы-теории алгоритмов в ее различных спецификациях— тезисов Чёрча, Тьюринга, Маркова? Вот что, например, говорит о своем тезисе сам автор «принципа нормализации: