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

Теорема 6.1. Композиция нормальных алгоритмов Ai,A2,..-An в алфавите А есть снова нормальный алгоритм (над алфавитом А ) . Ясно, что достаточно провести доказательство для композиции двух алгоритмов. Доказательство. Пусть Аи В - нормальные алгоритмы в алфа­ вите А . Сопоставим каждой букве а из ^ новую букву а , которую назовем двойникомб у к в ы а. При этом считаем, что для любой буквы а из А ее двойник не принадлежит ^4. Пусть А - алфавит, состоящий из всех двойников букв алфавита А . Выберем какие-нибудь две буквы, например, а и Р, не принадлежащие А и А . Обозначим через А'^ схему, полученную из схемы нормального алгоритма Л* заменой в ней всюду на "а". Обозначим через схему, полученную из В' заменой на "р", далее всех букв из А - их двойниками и затем заменой всех формул подстановок вида A-^Q формулами подстановок a —>aQ. Рассмотрим схему: а а —>а а ( а е А ) 1) а а —> а а ( а е А ) 2) аЬ — > аЬ (а,Ь е А) 3) ар—> ра (а е а) 4) Ра ->•ра ( а е А ) 5) аЬ - > аЬ (а,ЬеА) 6) а р -> оА V) йР 8) И " 9) 229