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

ЗамыканиемалгоритмаЛ называется алгоритм Л", полученный из А добавлением формулы подстановки Л-^»Л в качестве последней подстановки, т.е.: P2-^{*)Q2 Нам известно, что любой нормальный алгоритм заканчивает процесс переработки слова либо после применения заключительной подстановки, либо если все слова РьРъРъ.-'-, Р» не содержатся в слове, полученном при предыдущем шаге. Подстановка применима к любому слову. Следовательно, алгоритм Л * заканчивает переработку слов всегда по заключительной подстановке, которая есть либо некоторая из подстановок Р/->(в)6, (1:S i< п) либо Отметим, что подстановка Л—>®Л, добавленная к А для полу­ чения А \ стоит последней. Поэтому эта подстановка будет приме­ няться только тогда, когда не применимы все подстановки алгоритма А , причем применение Л—>»Л к любому слову не изменяет этого слова. Следовательно, результаты применения алгоритмов А иА ' к любому слову в А будут совпадать, т.е. алгоритмы А аА ' вполне эквивалентны. Пусть А - нормальный алгоритм в алфавите а алфавит А2 является расширением Ai, т.е. A1C1A2. Тогда можно рассмотреть нормальный алгоритм А^ в алфавите Аг с той же схемой, что и А . Очевидно, V? в алфавите ,/41: Л(Р) =А%Р), ' (6.1) т.е. А и А'^ вполне эквиваленты относительно A i . Нормальный алго­ ритм у4^будем называть естественным распространениемА на алфа­ вит ^2. 227