Если не сделано специальных оговорок, мы будем предполагать, что рассматриваемые функции y=f(x1,x2,…,xn) являются числовыми, их значения и аргументы принадлежат множеству натуральных чисел N={0,1,2,…}. Областью определения функции y=f(x1,x2,…,xn) может быть как все множество Nn, так и некоторая его часть. Допуская возможность того, что функция определена не на всем Nn, мы будем называть функцию частичной.
Далее мы определим простейшие функции и элементарные операции над функциями.
Простейшие функции:
1) S(x)=x+1 (функция следования);
2) O(x)=0 (тождественный ноль);
3) Pr[n;i](x1,x2,…,xn)=xi, n≥1 (проекции).
Заметим, что проекции Pr[n;i] составляют бесконечное семейство функций.
Элементарные операции над частичными функциями.
1. Суперпозиция (или композиция).
Пусть даны частичная функция
g(x1,x2,…,xm)
и частичные функции
f1(x1,x2,…,xn), …, fm(x1,x2,…,xn).
Суперпозицией функций g и f1,…,fm называется частичная функция
h(x1,x2,…,xn)=g(f1(x1,x2,…,xn),…,fm(x1,x2,…,xn)),
которая задается на наборе (x1,x2,…,xn) указанной формулой, если определены все значения y1=f1(x1,x2,…,xn), …, ym=fm(x1,x2,…,xn) и значение g(y1,y2,…,ym). В противном случае функция h(x1,x2,…,xn) считается неопределенной. Для функции h, полученной суперпозицией функций g и f1,…,fm, будем использовать обозначение h=Cn[g; f1,…,fm].
однозначно определяют функцию h(y). Последовательно вычисляя, находим:
h(1)=g(0,a); h(2)=g(1,h(1)); …
Пример.При a=1, g(y,z)=y⋅z уравнения
h(0)=1; h(y+1)=(y+1)h(y)
определяют функцию
h(y)=y!=1⋅2⋅3⋅…⋅y.
Пусть даны функции f(x) и g(x,y,z). Говорят, что функция h(x,y) получается из функций f и g (примитивной) рекурсией, если функция h удовлетворяет уравнениям:
h(x,0)=f(x); h(x,y+1)=g(x,y,h(x,y)).
Ясно, что функция h определена однозначно. Имеем:
h(x,1)=g(x,0,h(x,0))=g(x,0,f(x));
h(x,2)=g(x,1,h(x,1)); … .
Для функции h(x,y), полученной рекурсией из функций f и g, будем использовать обозначение h=Rc[f;g].
Примеры.Пусть f(x)=x (то есть f=Pr[1;1]) и g(x,y,z)=z+1 (то есть g=Cn[S;Pr[3,3]]). Тогда функция sum=Rc[f;g] определяется уравнениями
Пусть g(x,y,z)=z+x (то есть g=Cn[sum;Pr[3;3],Pr[3;1]]). Определим функцию prod(x,y) как prod=Rc[O;g]. Тогда h удовлетворяет уравнениям
prod(x,0)=0; prod(x,y+1)=h(x,y)+x.
Получаем:
prod(x,1)=h(x,0)+x=0+x=x;
prod(x,2) = h(x,1)+x = x+x = x⋅2; …,
и, вообще, prod(x,y)=xy.
Вообще говоря, в определении по рекурсии h=Rc[f;g] можно считать, что x представляет собой набор аргументов (x1,x2,…,xn). Тогда рекурсия по функциям f(x1,x2,…,xn), g(x1,x2,…,xny,z) определяет функцию h(x1,x2,…,xn,y).
Функции, которые могут быть получены из простейших функций операциями суперпозиции и рекурсии, называются примитивно рекурсивными.
если имеются значения y такие, что f(x1,x2,…,xn,y)=z, то h(x1,x2,…,xn,z) есть наименьшее из таких значений; в противном случае h(x1,x2,…,xn,z) не определено.
Для так определенной функции h будем писать h=Mn[f].
Если функция f(x1,x2,…,xn,y) частичная, то h=Mn[f] определяется следующими условиями:
h(x1,x2,…,xn,z)=y, если f(x1,x2,…,xn,y)=z, причем f(x1,x2,…,xn,t) определено и отлично от z для всех t<y; в противном случае h(x1,x2,…,xn,z) не определено.
Пример.Рассмотрим функцию h=Mn[sum]. Имеем
h(x,z)=min{y | x+y=z}.
Если x≤z, то h(x,z)=z−x, в противном случае h(x,z) не определено. Обозначим эту функцию через dif.
Частичные функции, которые могут быть получены из простейших с помощью конечного числа операций суперпозиции, рекурсии и минимизации, называются рекурсивными (или частично рекурсивными). Всюду определенные частично рекурсивные функции называются общерекурсивными. Запись частично рекурсивной функции с помощью простейших функций и операций будем называть рекурсивной схемой. Рекурсивная схема фактически задает алгоритм вычисления функции. По рекурсивной схеме функции f может быть построено ее рекурсивное описание: конечная последовательность частичных функций f0, f1, …, fn такая, что fn=f, и каждая функция в этой последовательности либо является простейшей, либо получается применением одной из элементарных операций к некоторым из предшествующих ей функций. Одна и та же функция может быть определена с помощью разных рекурсивных схем. Это согласуется с представлением о том, что одну и ту же функцию можно вычислять по-разному.
Пример. Имеем следующую рекурсивную схему для функции dif из предыдущего примера:
dif=Mn[Rc[Pr[1;1]; Cn[S;Pr[3,3]]]].
Из этой формулы без труда можно получить рекурсивное описание функции dif:
Pr[1;1], Pr[3,3], S, Cn[S;Pr[3,3]], Rc[Pr[1;1]],
Mn[Rc[Pr[1;1]; Cn[S;Pr[3,3]]]]=dif.
Рекурсивная схема представляет собой слово над счетным алфавитом, содержащим в качестве символов натуральные числа, обозначения для простейших функций, элементарных операций, скобки, запятую и точку с запятой. Следовательно, множество рекурсивных схем счетно. Вместе с ним счетно и множество частично рекурсивных функций.
