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

алгоритм В преобразует {KI^,K2, —,KN) в RJ F(KI,K2,-;K „)R2. Надо как- то изменить алгоритм, чтобы он убирал слова Ri и Rj. Пусть B j - нормальный алгоритм над стирающий все вхождения SQ перед первым вхождением 1 или * во всяком слове в алфавите Такой алгоритм можно задать схемой: В,= aS() a l н а * н а • 1 а ->«А А - > а Пусть i?2 - нормальный алгоритм над {1,*, J S 'O }, который стирает все вхождения So после последнего вхождения 1 или * во всяком слове в алфавите Например, Вг можно задать схемой: а * ->* а a l -> 1а В-у ~ ^ а а ->«А Л а Построим композицию алгоритмов В, BI и Вг. С=В2®ВХ»В. По доказанной теореме 6.1 алгоритм С является нормальным алгоритмом, как композиция нормальных алгоритмов. Для любых натуральных чисел к\,к2,...,к„ имеем В(^ki,k2,.:,k „^ = ^ = R\ f { k i , k 2 , - ; k n ) ^ 2 ' где/?1 и /?2- некоторые слова в {^о}. Далее ®1 (^1 ) ~ /(^1Дз'-"! ^п)^2 ' Отсюда видно, что / есть вычислимая по Маркову функция, ее вычисляет нормальный алгоритм С. Аналогичным образом проводится доказательство для частично вычислимых функций. 242