Рекурсивные функции

Если не сделано специальных оговорок, мы будем предполагать, что рассматриваемые функции y=f(x₁,x₂,…,x_n) являются числовыми, их значения и аргументы принадлежат множеству натуральных чисел N ={0,1,2,…}. Областью определения функции y=f(x₁,x₂,…,x_n) может быть как все множество N ⁿ, так и некоторая его часть. Допуская возможность того, что функция определена не на всем N ⁿ, мы будем называть функцию частичной.

Далее мы определим простейшие функции и элементарные операции над функциями.

Простейшие функции:

1) S(x)=x+1 (функция следования);

2) O(x)=0 (тождественный ноль);

3) Pr[n;i](x₁,x₂,…,x_n)=x_i, n≥1 (проекции).

Заметим, что проекции Pr[n;i] составляют бесконечное семейство функций.

Элементарные операции над частичными функциями.

1. Суперпозиция (или композиция).

Пусть даны частичная функция

g(x₁,x₂,…,x_m)

и частичные функции

f₁(x₁,x₂,…,x_n), …, f_m(x₁,x₂,…,x_n).

Суперпозицией функций g и f₁,…,f_m называется частичная функция

h(x₁,x₂,…,x_n)=g(f₁(x₁,x₂,…,x_n),…,f_m(x₁,x₂,…,x_n)),

которая задается на наборе (x₁,x₂,…,x_n) указанной формулой, если определены все значения y₁=f₁(x₁,x₂,…,x_n), …, y_m=f_m(x₁,x₂,…,x_n) и значение g(y₁,y₂,…,y_m). В противном случае функция h(x₁,x₂,…,x_n) считается неопределенной. Для функции h, полученной суперпозицией функций g и f₁,…,f_m, будем использовать обозначение h=Cn[g; f₁,…,f_m].

Примеры.

Cn[S;S](x)=S(S(x))=S(x+1)=x+2;

Cn[S;Cn[S;S]](x)=x+3;

Cn[O;Pr[n;1]](x₁,x₂,…,x_n)=O(Pr[n;1](x₁,x₂,…,x_n))=O(x_i)=0.􀀀

2. Рекурсия.

Начнем с частных случаев.

Пусть заданы функция g(y,z) и число a. Уравнения:

h(0)=a; h(y+1)=g(y,h(y))

однозначно определяют функцию 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] определяется уравнениями

sum(x,0)=x; sum(x,y+1) =g (x,y,sum(x,y)) = sum(x,y)+1.

Имеем:

sum(x,1)=sum(x,0)+1=x+1;

sum(x,2)=sum(x,1)+1=(x+1)+1=x+2, …

и, вообще, sum(x,y)=x+y.

Пусть 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 представляет собой набор аргументов (x₁,x₂,…,x_n). Тогда рекурсия по функциям f(x₁,x₂,…,x_n), g(x₁,x₂,…,x_ny,z) определяет функцию h(x₁,x₂,…,x_n,y).

Функции, которые могут быть получены из простейших функций операциями суперпозиции и рекурсии, называются примитивно рекурсивными.

3. Минимизация.

Пусть f(x₁,x₂,…,x_n,y) всюду определенная функция. Определим функцию h(x₁,x₂,…,x_n,z) условием:

если имеются значения y такие, что f(x₁,x₂,…,x_n,y)=z, то h(x₁,x₂,…,x_n,z) есть наименьшее из таких значений; в противном случае h(x₁,x₂,…,x_n,z) не определено.

Для так определенной функции h будем писать h=Mn[f].

Если функция f(x₁,x₂,…,x_n,y) частичная, то h=Mn[f] определяется следующими условиями:

h(x₁,x₂,…,x_n,z)=y, если f(x₁,x₂,…,x_n,y)=z, причем f(x₁,x₂,…,x_n,t) определено и отлично от z для всех t<y; в противном случае h(x₁,x₂,…,x_n,z) не определено.

Пример. Рассмотрим функцию h=Mn[sum]. Имеем

h(x,z)=min{y | x+y=z}.

Если x≤z, то h(x,z)=z−x, в противном случае h(x,z) не определено. Обозначим эту функцию через dif.􀀀

Частичные функции, которые могут быть получены из простейших с помощью конечного числа операций суперпозиции, рекурсии и минимизации, называются рекурсивными (или частично рекурсивными). Всюду определенные частично рекурсивные функции называются общерекурсивными. Запись частично рекурсивной функции с помощью простейших функций и операций будем называть рекурсивной схемой. Рекурсивная схема фактически задает алгоритм вычисления функции. По рекурсивной схеме функции f может быть построено ее рекурсивное описание: конечная последовательность частичных функций f₀, f₁, …, f_n такая, что f_n=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.

Рекурсивная схема представляет собой слово над счетным алфавитом, содержащим в качестве символов натуральные числа, обозначения для простейших функций, элементарных операций, скобки, запятую и точку с запятой. Следовательно, множество рекурсивных схем счетно. Вместе с ним счетно и множество частично рекурсивных функций.

Не нашли, что искали? Воспользуйтесь поиском: