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

^ f (Xi ,X2, ...,Хп ,0) =g (Xi ,X2,... ,Хп), а) J f(Xi,X2,...,X „,y +l)=h (Xi,X2,...,X„,y,f(Xi,X2,...,X„ , у)), при этом-исключается случай п=0, для которого: ^ f(0)=k, где к - фиксированное целое неотрицательное число, ) J f(y +I)=h (yj-(y))- в случае а) будем говорить, что функция / получена из g и /2 с помощью рекурсии, а xi,x2,...,x „ - параметры рекурсии, а в случае б) - что функция / получена из одной функции h с помощью рекурсии. Заметим, что функция / всегда определена: в случае а) значение f(xi,x2,...,x „,0) определяется из 1-го равенства, далее, если знаем f(xi,x2,...,x „,y), из 2-го равенства определяем f(xi,x2,...,x „,y +l), аналогично и для случая б). ц - оператор: пусть функция g(xi,x2 ,...,xn ,y) такова, что для любых xi,x2 ,...,xn существует, по крайней мере, одно значение при котором g(xi,x2,...,x „,y)=0. Обозначим через /Liy(g (xi ,x2 ,...,xn ,y)=0) наименьшее значение у, при котором g (Xi ,X2 ,...,Xn ,y)=0. Пусть f(xi,x2,...,xy)=iiy(g(xi,x2,...,xn,y)=0). Будем тогда говорить, что функция / получена из функции g с помощью //-оператора, если для любых xi,x2,...,xn существует, по крайней мере, одно значение для которого g (Xi ,X2 ,...,Xn ,y)=0. функция называется примитивно рекурсивной, если она может быть получена из исходных функций 1), 2) и 3) с помощью конечного числа подстановок и рекурсий. Функция / называется общерекурсивной, если она может быть получена из исходных функций 1), 2) и 3) с помощью конечного числа подстановок, рекурсий и //-оператора. Общерекурсивные функции иногда называют рекурсивными функциями. Из определений очевидно, что каждая примитивно рекурсивная функция является общерекурсивной, но не наоборот. Отметим, что примитивно и общерекурсивные функции являются всюду определенными функциями, так как исходные функции всюду определены, а подстановки, рекурсии и //-оператор не меняют всюду определенности. § 14. Примитивно рекурсивиость некоторых функций. Частично - рекурсивные функции Теорема 5.8. Следующие функции являются примитивно рекурсивными: 170