Математическая логика и теория алгоритмов

Pk-^{ »)Qk - простая формула подстановки, то применим к Ri тот же поиск, который был только что применен к i?o, и т.д. В случае, когда через конечное число шагов процесс преобразования закончится, то полученное слово i?/ и является результатом. Если же процесс переработки слова Rq бесконечен (никогда не заканчивается), то считаем, что алгоритм не применим к слову i?o. Нормальныйалгоритмнад алфавитомА отличается от нор­ мального алгоритма в алфавите А только тем, что в словах ?, и g, (!</'<«) могут использоваться не только буквы из алфавита А , но и буквы, не принадлежащие алфавиту^. Рассмотрим несколько примеров нормальных алгоритмов. 1. Пусть А={а,Ь,с}. Таблица формул подстановок а а I) В =•сс —> (®)с 2) b с 3) задает некоторый нормальный алгоритм В в алфавите А . Если взять слово Ro=bb, то В преобразует его сначала с помощью подстановки 3) в слово сЬ, затем, вновь применяя подстановку 3), получим сс. Далее, по заключительной подстановке 2), получим с. Это слово и будет В Ш Если исходное слово R q будет содержать букву а, то В не при­ меним к Ко, ибо подстановка 1) будет применяться безостановочно. 2. Пусть А={а,Ь,с}. Рассмотрим таблицу формул подстановок В = ра Рс Р Л - > - > - > «Р бр ср •а Р 1) 2) 3) 4) 5) Это таблица, очевидно, задает нормальный алгоритм над алфа­ витом А , ибо Р € Если взять произвольное слово R q В ТО К нему сначала подстановки 1), 2) и 3) не применимы, так как слов Ра, и Рс в слове Rq быть не может. Подставив вместо самого левого 222