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

в, ОС S q —^ ос al^ »l cir* ^ * Л—^ ос В, а * *а al^la OCSq а а^»А у1 —^ о^ Построим композицию алгоритмов В, Bj и В2: C=B2*Bj »B. По доказанной теореме 5.1 алгоритм С является нормальным алгоритмом, как композиция нормальных алгоритмов. Для любых натуральных чисел ki,k2,...,kn имеем в[(к^,к2,...,к„))=Ат^^[(к^,к2,...,к„))=Щ1(к^,к2,...,к„)К2, где Ri и i?2 - некоторые слова в {So}. Далее ^7 ( ^ 1Ж ^2V - ) ^ 2 )= Ж ^2V - ) ^ 2 ; B2{f(kj,k2,...,k „)R2)=f(ki,k2,...,kn)- Отсюда видно, что / есть вычислимая по Маркову функция, ее вычисляет нормальный алгоритм С. Аналогичным образом проводится доказательство для частично вычислимой функции. Теорема 5.6 (обратная теореме 5.5).Пусть В- нормальный алгоритм в алфавите А, не содержащем SgVi. д. Тогда существует такая машина Тьюринга Т, что алгоритм Тьюринга в алфавите ^cv/So, ^ обладает следующим свойством: для всякого слова Р в А алгоритм A t , au { S o ,^ применим к Р тогда и только тогда, когда к Р применим алгоритм В и при этом Ат,Аи[8о,&}(Р) имеет вид S q B { p ) S q , где у ит целые неотрицательные числа, а S q = S q S q ...S q к раз Согласно сформулированной теореме значения алгоритмов В и Af^uiSo.b} формально различны, так как для машины Тьюринга So есть символ пустого квадрата, а в нормальном алгоритме В 5'о-буква, равноправная с любой другой буквой. По с точностью до символов So, которые могут стоять справа и слева от результирующего слова, алгоритмы В vi. Atau{So,?,} вполне эквиваленты. Теорему принимаем без доказательства. Следствие 5.2. Всякая частично вычислимая (вычислимая) по Маркову функция частично вычислима (вычислима) по Тьюрингу. Доказательство следствия сразу получается из теоремы 5.6 и определения вычислимой по Тьюрингу функции. Из теоремы 5.5 и 5.6 видим, что различные подходы к понятию алгоритмов Тьюринга и Маркова (нормальные алгоритмы) по существу эквивалентны, т.е. то, что можно осуществить с помощью нормального алгоритма, можно осуществить с помощью машины Тьюринга, и наоборот. 163