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

тарные операции. В качестве элементарной операции, на базе которой будут строиться нормальные алгоритмы, выделим подстановку одного слова вместо другого. Пусть задан алфавит А , не содержащий в качестве букв символов "в" и и пусть Р и Q - слова в алфавите А . Тогда выражения P-^Q,P-^<^Q называются формулами подстановки в алфа­ вите ^4. Формула подстановки называется простойподстановкой и означает, что вместо Р нужно подставить слово Q и перейти к следующей подстановке. Формула подстановки P-^^Q называется з а к л ю ч и т е л ь н о й подстановкой и означает, что вместо Р нужно подставить Q и закон­ чить процесс преобразования. Пусть P-^{f)Q означает любую из формул подстановки P-^Q или P-^ «Q. Нормальныйалгоритм в алфавитеА считается заданным, если задана конечная таблица (схема) формул подстановок слов алфавита^: Р2 (*)в2 И = ' « > 1, Р/ и QI, (!</<«) - слова в А, причем согласно этой таблице (схеме) формул подстановок можно осуществлять преобразование слов алфавита^ следующим образом. Пусть R q слово в алфавите А. Если ни одно из Р\,Р2,...,РП не входит в i?0) то процесс применения В К КО заканчивается и его результатом считается слово Ro, Если хотя бы одно из РьРъ.--,Рц входит в Ro, то отыскиваем самую первую (в порядке следования в таблице) формулу подстановки, такую, что Pk входит в Ro. Совершаем подстановку слова Qk вместо самого' левого вхождения слова РК в слово R q . Пусть R] - результат такой подстановки. Если использованная подстановка Pk-^{o)Qk - заключительная, то работа алгоритма заканчивается и его результатом считается R\. Если 221