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

буква из A2\Aj . Получившийся нормальный алгоритм называют формальным распространением А на алфавит А2. Очевидно, что формальное распространение алгоритма А вполне эквивалентно алгоритму А относительно ^7 и не применимо к тем словам ъА2, которые не являются словами ^Ai. Использование возможности распространения нормального алгоритма на более широкий алфавит позволяет во многих случаях опускать без особого уш,ерба точности упоминание об алфавитах, в которых строятся конкретные нормальные алгоритмы. § 6. Операции над нормальными алгоритмами Композиция алгоритмов. Пусть Л и в - два алгоритма в алфавите А. Композицией алгоритмов Л и в в алфавите А называют алгоритм С такой, что IzP в ^ : С {Р) =В {А (Р)). Таким образом, композиция алгоритмовЛ и в представляет собой алгоритм, получаюш,ийся в результате последовательного применения алгоритмов к заданному слову Р, что можно продемонстрировать следуюш,ей блок-схемой (рис.5.1). Композиция алгоритмовЛ и в обозначается как: С =В °А. Пусть Ai,A2,...,An - алгоритмы в алфавите А, тогда под An °An.i° ... °Ai будем понимать следуюш,ее: АЛАП.Л..ЛЛ З %А 2° А 1))...)). Теорема 5.1. Композиция нормальных алгоритмов Л 7, Л 2, . . .в алфавите А есть снова нормальный алгоритм (над алфавитом ^4). Ясно, что достаточно провести доказательство для композиции двух алгоритмов. Доказательство. Пусть Л и в - нормальные алгоритмы в алфавите А. Сопоставим каждой букве а ш А новую букву а , которую назовем двойником буквы а. При этом считаем, что для любой буквы а ш А qq ДВОЙНИК не принадлежит А. Пусть А - алфавит, состояш,ий из всех двойников букв алфавита А. Выберем какие нибудь две буквы, например, cir и , не принадлежаш,ие АиА. Обозначим через А" схему, полученную из схемы нормального алгоритма Л'заменой в ней всюду на Обозначим через схему, полученную из В' заменой на далее всех букв из Л - их двойниками и затем заменой всех формул подстановок вида A-^Q формулами подстановок a-^oQ. Рассмотрим схему: р А (Р) В (А (Р)) А В Рис. 5.1. 153