Математическая логика и теория алгоритмов. Для изучающих компьютерные науки

в Pi ^ ( «fe Р2 i*)Q2 Рп (*)Qn п > 1, Pi и Qi, (1<1^) - слова в А, причем согласно этой таблице (схеме) формул подстановок можно осуществлять преобразование слов алфавита А следующим образом. Пусть КО слово в алфавите А. Если ни одно из PI,P2,...,PN не входит в RO, то процесс применения В к Ro заканчивается и его результатом считается слово Ro. Если хотя бы одно из Pi,P2,...,Pn входит в Ro, то отыскиваем самую первую (в порядке следования в таблице) формулу подстановки, такую, что PK входит в RO. Совершаем подстановку слова Qk вместо самого левого вхождения слова Pk в слово Ro. Пусть Ri - результат такой подстановки. Если использованная подстановка Pk^(*)Qk - заключительная, то работа алгоритма заканчивается и его результатом считается RI. Если Pk^(*)Qk - простая формула подстановки, то применим к Ri тот же поиск, который был только что применен к Ro, и так далее. В случае, когда через конечное число шагов процесс преобразования закончится, то полученное слово RI и является результатом. Если же процесс переработки слова RO бесконечен (никогда не заканчивается), то считаем, что алгоритм не применим к слову RO. Нормальный алгоритм над алфавитом А отличается от нормального алгоритма в алфавите А только тем, что в словах Pi и Qi могут использоваться не только буквы из алфавита^, но и буквы, не принадлежащие алфавиту Рассмотрим несколько примеров нормальных алгоритмов. 1. Пусть А={а,Ь,с]. Таблица формул подстановок В= \ а ^ а (1) сс (•) € (2) b ^ с (3) задает некоторый нормальный алгоритм В в алфавите А. Если взять слово Ro=bb, то В преобразует его сначала с помощью подстановки (3) в слово сЬ, затем, вновь применяя подстановку (3), получим сс. Далее, по заключительной подстановке (2), получим с. Это слово и будет SfKJ. Если исходное слово Ro будет содержать букву а, то В не применим к R ибо подстановка (1) будет применяться безостановочно. 2. Пусть А={а,Ь,с}. Рассмотрим таблицу формул подстановок О? 149