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

Заметим, что функция/всегда определена: в случае а) значение J[x\rX2,...,Xi „0) определяется из 1-го равенства, далее, если знаем из 2-го равенства определяем анало­ гично и для случая б). j j .-оператор". пустьфункция g { X \ , X 2 , . . ; X „ , y ) такова, чтодля любых XI,X2, —,XN существует, по крайней мере, одно значение у , при котором g(XuX2,...,X „,y)^Q. Обозначим через |a,y(g(xi,x2,...,^n,>')=0) наименьшее значение у , при котором Пусть f{xi,X2,...,x „)=]xy(g{xuX2,...,x„,y)=Q). Будем тогда говорить, что функция / получена из функции g с помощью ц-оператора, если для любых Xi,X2,...,x „ существует по крайней мере одно значение >, для которого Функция называется п р и м и т и в н о - р е к у р с и в н о й , если она монсет быть гюлучена из исходных функций 1), 2) и 3) с помощью конечного числа подстановок и рекурсий. Функция / называется о б щ в р е ж у р с и в н о й , если она может быть получена из исходных функций 1), 2) и 3) с помощью конечного числа подстановок, рекурсий и ц-оператора. Общерекурсивные функции иногда называют рекурсивными функциями. Из определений очевидно, что каждая примитивно-рекурсивная функция является общерекурсивной, но не наоборот. Отметим, что примитивно и общерекурсивные функции явля­ ются всюду определенными функциями, так как исходные функции всюду onpefleJreHbr, а подстановки, рекурсии и ц-оператор не меняют всюду определенности. 255