Кратко обсудим третий подход к уточнению (конкретизации) понятия алгоритма. По смыслу оно близко к идеям Тьюринга, однако, в нем не используются представления о каких-либо машинах. Алгоритм задается системой подстановок, которые указывают, какие замены символов необходимо производить и в каком порядке эти подстановки должны следовать. Такой подход был предложен А. А. Марковым. В начале 50-х годов было введено понятие нормального алгоритма (сам Марков называл их алгорифмами).
Вновь рассмотрим некоторый алфавит А, содержащий конечное число знаков (букв). Введем ряд определений:
Слово - это любая конечная последовательность знаков алфавита
Число символов в слове называется его длиной.
Слово, длина которого равна нулю, называется пустым.
Слово s называется подсловомслова q, если q можно представить в виде q - rst, где rut- любые слова в том же алфавите (в том числе и пустые).
Теперь можно определить понятие алгоритма (не являющееся строгим):
Алгоритмом в алфавите А называется эффективно вычислимая функция, областью определения которой служит какое-либо подмножество множества всех слов в алфавите А и значениями которой также являются слова в алфавите А.
В алгоритмах Маркова в качестве элементарного шага алгоритма принимается подстановка одного слова вместо другого. Пусть в алфавите А построено исходное слово Р, которое содержит подслово Рr (в общем случае таких подслов в исходном слове может быть несколько), а также имеется некоторое слово Pk в том же алфавите.
Подстановкой называется замена первого по порядку подслова Рr исходного слова Р на слово Pk. Обозначается подстановка Рr→ Pk.
Алгоритм в данной форме представления задается системой подстановок, которая представляет собой последовательность (список) подстановок. Если в этом списке имеются подстановки с левыми частями, которые входят в Р, то первая из них применяется к Р, в результате чего оно переходит в другое слово P1. К нему вновь применяется схема подстановок и т.д. Процесс прекращается в двух случаях: либо в списке не нашлось подстановки с левой частью, входящей в Рn, либо при получении Рn была применена последняя подстановка.