2.1.3. Нормальный алгоритм а.А. Маркова

Говорят, что задан алгоритм в алфавите А, который применим к слову L и преобразует его в слово M, если отправляясь от L и действуя согласно инструкциям, в конце концов получим M, на котором процесс заканчивается.

Множество слов, к которым применим данный алгоритм, называется его областью применения. Два алгоритма называются эквивалентными, если их области применения совпадают и результаты преобразования ими любого слова совпадают.

А.А. Марков ввёл определённые указания о порядке использования подстановок в алгоритме. Определение нормального алгоритма Маркова сводится к следующему. Задаётся алфавит А и фиксируется в опреде-лённом порядке система ориентированных подстановок. Исходя из про-извольного слова R в алфавите А, просматриваются подстановки в таком порядке, в котором они заданы. Первая встретившаяся подстановка P1: L1  M1 с левой частью, входящей в R, используется для преобразования слова R, в которое вместо первого вхождения левой части подставляется его правая часть, в результате чего получаем новое слово R1: P1 (R) = R1. Далее процесс повторяется исходя из слова R1, затем из R2 и т. д. до тех пор, пока он не остановится.

Признаки остановки

1. Слово Rn не содержит ни одной из левых частей допустимых подстановок.

2. Для получения Rn использована последняя подстановка.

Пример 2.1. Заданы алфавит А = {1, +} и система подстановок: +  # (# — пустое слово); 11.

Слово 111 + 11 + 1111 + 1 этот алгоритм преобразует следующим образом:

0 - шаг 111 + 11 + 1111 + 1

1 - шаг 11111 + 1111 + 1

2 - шаг 111111111 + 1

3 - шаг 1111111111

4 - шаг 1111111111

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

Эквивалентный ему алгоритм можно задать с помощью системы подстановок: 1 +  + 1, + 1 1, 1  1.

Накопленный опыт позволил высказать смелую гипотезу: любой алгоритм может быть представлен в виде нормального алгоритма Маркова. Иначе говоря, нормальный алгоритм Маркова можно использовать в качестве стандартной формы любого алгоритма.

2.2. Вычислимые и рекурсивные функции

Арифметическая функция y=(x₁, x₂, ...,x_n) - это целочисленная функция, зависящая от целочисленных значений аргументов, т.е. это фун-кция, построенная на множестве {0, 1, 2, ...}. Под  понимается суперпози-ция операций сложения, вычитания, умножения и деления, операций определения абсолютного значения результата при вычитании и целой части - при делении, а также некоторых специальных операций, например

min(x, y) = .

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

Арифметические функции, значения которых можно вычислять посред-ством некоторого алгоритма, называются вычислимыми функциями. Поня-тие вычислимой функции, основанное на интуитивном смысле алгоритма, также является интуитивным. Однако между ними имеется существенная разница: совокупность вычислительных процессов, удовлетворяющих приз-накам 1-5 алгоритма (п. В.1), очень обширна; напротив, совокупность вычис-лимых функций для самых разных процессов, удовлетворяющих признакам 1-5, оказалась одной и той же, и при том легко описываемой в обычных математических терминах. Точно описанная совокупность арифметических функций, совпадающая с совокупностью всех вычислимых функций при самом широком до сих пор известном понятии алгоритма (см. признаки 1-5), носит название совокупности рекурсивных функций.