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

в результате Я>^,у)~х+у получается рекурсией из примитивно- рекурсивных функций и A(x,y,z)=JV(z), следовательно, / - примитив но-ре курсивна, 2. Обозначим функцию умножения х на >< через \\i . Тогда v|i(x,0)=x' »0 = О = Z(x); )=xe(yi-l )=л-ву+л:=1(;(л:,у)+х=Д1|/(л:,>')^)=^г * х,у, Ц1{х,у)), где h * ( x , y ^ ) =Дх,2). Итак, получается рекурсией из примитивно рекурсивных функций g * { x ) = Z { x ) и h*(x^,z)=J{x,z), следовательно, функция - примитивно-рекурсивна. 3. Обозначим функцию возведения в степень через ф. Для ариф­ метических функций полагаем, что для любых целых х, в том числе и длях=0, т. е. 0°=1 (ф(0,0)=1). Получим ф ( х , 0 )=х ° =1=ВДх ) ) ; ф(х,>'+1)=У'^'=л:^вл:=ф(х,>') вх=\|/(ф(л:,у),л:)=/г**(л,у,ф(х,>')), где h**(x,y,z)= \\i(x,z), т.е. ф получается рекурсией из примитивно- рекурсивных функций g**(x)=N(Z{x)) и h**ix,y,z)=\\i(x,z), следова­ тельно, ф - примитивно-рекурсивна. Аналогичным образом доказывается и для функций 4)-15). Из теоремы следует, что примитивно-рекурсивные функции образуют достаточно широютй класс всюду определенных функций. Рассмотрим, как можно вычислять значения примитивно рекурсивных функций. Каждая примитивно-рекурсивная функция получается из исходных функций 1), 2) и 3) с помощью конечного числа подстановок и рекурсий. Представление функции с помощью подстановки и рекурсии, примененных к исходным функциям, можно рассма'фивать как набор инструкций для "механического" вычисления значения функций. Следовательно, доказательство примитивно-рекур- сивности функции является одновременно доказательством сущест­ вования алгоритма вычисления значений функций. Рассмотрим, например, функцию \\/(х,у)= х ^ у . Установлено, что \\j(x,Q) = Z(x)=0; \|/(А-,у+1)=Ду (х,у),х), гдеЛх.у)'=х+у. 257