Примеры решения задач

1. Доказать, что следующие функции являются примитивно рекурсивными.

a) f(x)=x+n

Решение. Функция f(x) может быть получена с помощью n-кратного применения оператора суперпозиции к простейшей функции s(x).

b) f(x,y)=x+y

Решение. Функция f(x) может быть задана следующей схемой примитивной рекурсии:

f(x, 0) = x = I¹₁(x),

f(x, y+1) = x+y+1=f(x,y)+1=s(f(x,y))=s(I³₃(x,y,f(x,y))).

Здесь функция g(x) имеет вид g(x)= I¹₁(x) и является, как и полагается, функцией одной переменной. А функция h(x,y,z) имеет вид h(x,y,z)=s(I³₃(x,y,z)) и является функцией трех переменных.

Заметим, что функции g(x) и h(x,y,z) являются прф, т.к. g(x) – третья простейшая функция, а h(x,y,z) может быть получена из простейших функций s(x) и I³₃(x,y,z) с помощью применения оператора суперпозиции.

Так как функцию f(x,y) можно получить с помощью оператора примитивной рекурсии из примитивно рекурсивных функций g(x) и h(x,y,z), то f(x,y) – прф.

с) f(x,y)=xy

Решение. Функция f(x) может быть задана следующей схемой примитивной рекурсии:

f(x, 0) = 0 = o(x),

f(x, y+1) = x(y+1)=xy+x=f(x,y)+x= I³₃(x,y,f(x,y)))+ I³₁(x,y,f(x,y))).

Так как функцию f(x,y) можно получить с помощью оператора примитивной рекурсии из примитивно рекурсивных функций g(x)=o(x) и h(x,y,z) = I³₃(x,y,z)) + I³₁(x,y,z)), то f(x,y) – прф.

2. Пусть g(x₁, ..., x_n,y) примитивно рекурсивная функция. Доказать, что следующая функция примитивно рекурсивна:

Решение. Особенность этой функции заключается в том, что суммирование ведется по переменному числу слагаемых. Однако функция fⁿ⁺¹ может быть задана следующей схемой примитивной рекурсии:

f(x₁, ..., x_n, 0) = g(x₁, ..., x_n,0) – прф,

f(x₁, ..., x_n, y+1) = = f(x₁, ..., x_n, y) + g(x₁, ..., x_n,y+1) – сумма прф g и самой функции f.

3. Доказать, что следующая функция частично рекурсивна.

Решение. Покажем, что функция f(x,y) может быть получена с помощью оператора минимизации.

Пусть xy, тогда f(x,y) определена и принимает некоторое значение: f(x,y) = xy = z. Как вычислить z? Можно предложить следующий способ: начиная с нуля перебирать по порядку все значения z, пока не выполнится условие xy=z, или xyz=0. Такое z обязательно найдется, т.к. xy0. Если же xy<0, то ни какое натуральное z не подойдет.

Программист записал бы это так:

unsigned int f(x,y)

{

z=0;

while((xyz)!=0) z++;

return z;

}

То же самое можно записать и в терминах оператора минимизации:

f(x, y)=z[|x–y–z|=0]

Модуль необходим для того, чтобы функция g(x,y,z)=|x–y–z| была определена, даже если x–y<0. Заметим, что g(x,y,z)=|x–y–z| является примитивно рекурсивной, т.к. может быть получена с помощью конечного числа применений оператора суперпозиции к простейшим функциям.

Поэтому f(x,y) – чрф.