Задание 12.

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

а) f(x, у) = х + у

Решение: возьмем в качестве функций g(x) и h(x, y, z) следующие простейшие всюду определенные функции: ,

По схеме примитивной рекурсии f (x, 0) = g (x) = x

f (x, y +1) = h (x, y, f (x, y)) = f (x, y)+1

В частности, f (x, 1) = x +1, f (x, 2) = x +2 и т.д.

Следовательно, f (x, y) = x + y

б) f(x, у) = х × у

Решение: возьмем в качестве функций g(x) и h(x, y, z) следующие всюду определенные примитивно рекурсивные функции: g (x) = 0(x), h(x, y, z) = (операция суммирования определена выше).

По схеме примитивной рекурсии f (x, 0) = g (x) = 0, а

f (x, y +1) = h (x, y, f (x, y)) = x + f (x, y)

В частности, f (x, 1) = x, f (x, 2) = x+ x = 2 x f (x, 3) = 3 x

Следовательно, f (x, y) = x × y

в) f(x, у) = х^у (0⁰ = 1 – принимаем по определению)

Решение: возьмем в качестве функций g(x) и h(x, y, z) следующие всюду определенные примитивно рекурсивные функции: g (x) = S(0(x)), h(x, y, z) = (операция умножения определена выше).

Тогда f (x, 0) = 1 f (x, у+ 1) = х × f (x, y)

f (x, 1) = x, f (x, 2) = x ², f (x, 3) = x ³ и т.д.

Следовательно, f (x, y) = х^у

г)

Решение: возьмем в качестве функций g(x) и h(x, y) следующие всюду определенные примитивно рекурсивные функции: ,

По схеме примитивной рекурсии

f (0) = g(0)=0, f (x +1) = h (x, f (x))

Тогда f (1) = h(0, f(0)) = 0+0(f (0)) = 0, f (2) = h (1, f (1))=1+0(f (1)) = 1, f (3) = 2+0 = 2

и т.д.

То есть, для