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

в иекоторых случаях удобнее, чтобы алгоритм удовлетво­ ряющий (6.1), был не применим к тем словам в Аг, которые не являются словами в Ai. Этого легко достигнуть, приписав к схеме ^4 сверху формулу вида х->х, где х - любая буква из Получившийся нормальный алгоритм называют формальным р а с п р о с т р а н е н и е м А на алфавит A i . Очевидно, что формальное распространение алгоритма А вполне эквивалентно алгоритму А относительно А\ и не применимо к тем словам в Аг, которые не являются словами в ^i. Использование возмолсности распространения нормального алгоритма на более широкий алфавит позволяет во многих случаях опускать без особого ущерба точности упоминание об алфавитах, в которых строятся конкретные нормальные алгоритмы. § 6. Операции над нормальными алгоритмами Композиция алгоритмов. Пусть А м В — два алгоритма в алфа­ вите Л . Композицией алгоритмов Л и В в алфавите А называют алгоритм Стахсой, что\/7^ кА : С(Р) s В ( А ( Р ) ) . Таким образом, композиция алгоритмов А и В представляет собой алгоритм, получающийся в результате последовательного при­ менения алгоритмов к заданному слову Р , что -молено продемонст­ рировать блок-схемой, представленной на рис. 6.1. Рис. 6.1 Композиция алгоритмов А и В обозначается как: С=В°А. Пусть Ai,A%...,An - алгоритмы в шк1)авите А , тогда под A , ° A „ . i ° ... ° A i будем понимать следуюп^ее: Р А В(А(Р)) A „ \ A , , . i % . . W ( A y ° A O ) . . . ) ) . 2 2 8