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

Если же машина Т не изменяет буквы S /d, а читающая головка движется, например, вправо по команде qoSkiRqr, то по подстановке qoSk\Si~^ Sk\q^! ( S j e A ) алгоритма Б из (6.2) получим Ясно, что и любому другому такту машины Т будет соответст­ вовать такое же преобразование слова с помощью алгоритма В за исключением того, что при преобразовании с помощью В в слове у нас всегда имеется некоторое д/, которого нет на ленте машины. Однако в конце преобразования алгоритм В своей подстановкой <7,—уберет эту лишнюю букву. Итак, ^ Р в А : Л г , л { Р ) =В{Р , что и требовалось доказать. С л е д с т в и е 6 . 1 . Всякая частично вычислимая (вычислимая) по Тьюрингу функция является частично вычислимой (вычислимой) по Маркову функцией. Доказательство. Пусть функция fix\,x2,...,x,^ вычислима по Тьюрингу и ее вычисляет машина Тьюринга Т с алфавитом А , содер­ жащим 1 и *. Это означает, что для любых натуральных чисел к\,к2 к„ найдутся такие слова R\ и Ri (возможно, пустые) в алфавите {i^c},чтоЛт^А{к1,к2,...,к„) - R\fikuk2,--,k „)R2. В силу доказанной теоремы 6.5 существует нормальный алгоритм В над А, вполне эквивалентный относительно А алгоритму А Г , А , т.е. для любых натуральных чисел к],к2,...,к„ имеем; ^rM((^b^2v-,^ «)) =- S ( ( ^ i ^ 2 v ^ „ ) ) s R ] f ( , k ^ , k 2 , . . . , k n ) R 2 - Для того, чтобы функция была частично вычислимой по Мар­ кову, нужно, чтобы существовал нормальный алгоритм, который преобразует (k.i,k2,...,k „) в f{k.i,k2,...,k „). Наш же нормальный 241