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

Если алгоритм В не применим к слову R=A{P), то и алгоритм С будет не применим к Р вследствие того, что 8) будет бесконечно перерабатывать слово аЬщ Ь„^ ,..Ьп^ • Если алгоритм В применим к слову R-A{P), то в результате его применения мы получили бы слово В{А{Р)), например: В{А{Р)) = с,„^ с„,^...с,„^ . еЛ, !</</) Тогда, как легко видеть, в результате применения 8) получим а Cm, Ст^-.-Ст^ Р ''X+i • ^ 1 / )• Теперь 5-кратное применение 4) приводит к слову (X р Сш| Ст2--- Cni • Далее, применяя 5), а затем (/-1) раз 6), имеем ^ Р — CtP5(yi(P)). Применяя заключительную подстановку 7), получим результат: Б{А{Р)). Таким образом, С(Р) =В{А{Р)), и, так как слово Р было произ­ вольным, теорема доказана. Соединение алгоритмов. Теорема 6.2. Пусть Ль Ло,.,,,нормальные алгоритмы в ал­ фавитах АЬА 2,,.., А „ соответственно и пусть А - объединение этих алфавитов. Тогда существует нормальный алгоритм В над А, назы­ ваемый соединением алгоритмовЛьЛ2,...,^и такой, что УРвА: Б(Р) =Аг' {Р)А/ (Р)-Л/ {Р)> гдел / - есть естественное распространение ^4, на^. Теорему примем без доказательства. Доказательство можно уви­ деть , например, в работе [21]. Разветвление алгоритмов. Пусть заданы алгоритмы А и В в алфавите А и некоторое условие U. Тогда можно задать предписание следующего типа: для данного слова Р в алфави­ те А проверить, удовлетворяет ли оно условию U. Если удовлетворяет, 231