Нормальные алгоритмы Маркова

Коротко обсудим 3-ий подход к уточнению (конкретизации) понятия метода. По смыслу оно близко к идеям Тьюринга, но, в нем не употребляются представления о каких-то машинах. Метод задается системой подстановок, которые указывают, какие подмены знаков нужно создавать и в каком порядке эти подстановки должны следовать. Таковой подход был предложен А. А. Марковым. Сначала 50-х годов было введено понятие обычного метода (сам Марков называл их алгорифмами).

Вновь разглядим некий алфавит А, содержащий конечное число символов (букв). Введем ряд определений:

Слово — это неважно какая конечная последовательность символов алфавита

Число знаков в слове именуется его длиной.

Слово, длина которого равна нулю, именуется пустым.

Слово s именуется подсловом слова q, если q можно представить в виде q — rst, где rut- любые слова в том же алфавите (в том числе и пустые).

Сейчас можно найти понятие метода (не являющееся серьезным):

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

В методах Маркова в качестве простого шага метода принимается подстановка 1-го слова заместо другого. Пусть в алфавите А выстроено начальное слово Р, которое содержит подслово Р_r (в общем случае таких подслов в начальном слове может быть несколько), также имеется некое слово P_k в том же алфавите.

Подстановкой именуется подмена первого по порядку подслова Р_r начального слова Р на слово P_k. Обозначается подстановка Р_r→ P_k.

Метод в данной форме представления задается системой подстановок, которая представляет собой последовательность (перечень) подстановок. Если в этом перечне имеются подстановки с левыми частями, которые входят в Р, то 1-ая из их применяется к Р, в итоге чего оно перебегает в другое слово P₁. К нему вновь применяется схема подстановок и т.д. Процесс прекращается в 2-ух случаях: или в перечне не нашлось подстановки с левой частью, входящей в Р_n, или при получении Р_n была использована последняя подстановка.