|
Может случиться, что на каком‑то такте работы алгорифма ни одна из формул подстановок (ни одна из команд) не окажется применимой. Тогда произойдет естественный обрыв процесса переработки слов, и слово, при этом полученное, считается результатом. Если же в процессе применения алгорифма к некоторому слову не происходит ни естественного обрыва процесса, ни применения заключительной формулы подстановки–то есть если процесс переработки исходного слова продолжается неограниченно долго, то считается, что алгорифм к этому слову не применим. Описанные правила настолько элементарны, что мы предоставляем читателю самостоятельно проследить за действием алгорифма 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 году была опубликована теорема, доказанная учеником А. А. Маркова В. К. Детловсом, о том, что всякий процесс, осуществимый с помощью нормального алгорифма, осуществим также посредством некоторой рекурсивной функции. Это значит, что рекурсивные функции и машины Тьюринга «равнообъемны» нормальным алгорифмам и что тезисы Чёрча и Тьюринга получают подкрепление в виде принципа нормализации (это название предложено А. А. Марковым; можно условиться называть этот принцип и по‑другому, например, тезисом Маркова): всякое точное общепонятное предписание, определяющее произвольный потенциально осуществимый процесс переработки слов в каком‑либо алфавите, ведущий от варьируемых исходных данных к некоторому результату, эквивалентно некоторому нормальному алгорифму . — 104 —
|