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

обозревает символ Su. Дальнейшие ее действия определены ее командами. Из подстановок алгоритма В к слову Р будет сначала применима только последняя подстановка, в результате которой получим слово QO Slcl,Slc2,...Slan- (^'2) Если среди команд машины Т имеется команда, по которой стирается буква SKI и заменяется, например, буквой S/S je A), т.е. имеется команда qoS^Sj -qr, то по подстановке qoSu^rSj алгоритм преобразует слово (5.2) в слово Я^г Sj Sk2- ••Sjqyi. Если же машина Т не изменяет буквы а читаюш,ая головка движется, например, вправо по команде qgSuRqr, то по подстановке qoS^Si^ SuqrSi (S ie A) алгоритма В получим SkiqrSk2- ••Skm- Ясно, что и любому другому такту машины Т будет соответствовать такое же преобразование слова с помош,ью алгоритма В за исключением того, что при преобразовании с помош,ью В в слове у нас всегда имеется некоторое qi, которого нет на ленте машины. Однако в конце преобразования алгоритм В своей подстановкой qi —>»A уберет эту лишнюю букву. Итак, \/Р в А :Аг,а( Р )=В( Р), что и требовалось доказать. Следствие 5.1. Всякая частично вычислимая (вычислимая) по Тьюрингу функция является частично вычислимой (вычислимой) по Маркову функцией. Доказательство. Пусть функция f(xi,x2,...,xn) вычислима по Тьюрингу и ее вычисляет машина Тьюринга Тс алфавитом^, содержаш,им 1 и *. Это означает, что для любых натуральных чисел ki,k2,...,kn найдутся такие слова Rj и R2 (возможно, пустые) в алфавите {So}, что Ат ,А (к],к2 ,...,кп) =Ri f (kj,k2,...,kn)R2- В силу доказанной теоремы 6.5 суш,ествует нормальный алгоритм В над А, вполне эквивалентный относительно А алгоритму Ат , а , т.е. для любых натуральных чисел ki,k2,...,kn имеем: AT,A((kj,k2,...,kJ) =B((kj,k2,...,kJ) = Rif(kj,k2,...,kJR2. Для того, чтобы функция была частично вычислимой по Маркову, нужно, чтобы существовал нормальный алгоритм, который преобразует (kj,k2,...,kn) в f (kj,k2,...,kn). Наш же нормальный алгоритм В преобразует (kj,k2,...,kn) в Ri f (kj,k2,...,k „)R2. Надо как-то изменить алгоритм, чтобы он убирал слова и R2. Пусть В] - нормальный алгоритм над {l,^\So}, стирающий все вхождения So перед первым вхождением 1 или * во всяком слове в алфавите {l,^,So}. В2 - нормальный алгоритм над {l,^,So}, который стирает все вхождения So после последнего вхождения 1 или * во всяком слове алфавита {l,^,So}. Эти алгоритмы можно задать схемами: 162