Теория алгоритмов ДГТУ

ЗАДАЧА 1. Пусть n Є N. Доказать примитивную рекурсивность функции f(x) = x + n.

ЗАДАЧА 2. Доказать, что всякая примитивно рекурсивная функция является всюду определенной функцией.

ЗАДАЧА 3. Пусть n—произвольное натуральное число. Доказать примитивную рекурсивность следующей функции.

6) f(x) = xn.

ЗАДАЧА 4. Доказать, что следующие функции частично рекурсивны. Какие из этих функции примитивно рекурсивны, а какие частично рекурсивны, но не примитивно рекурсивны?

2) f(x, y) = x + xy

ЗАДАЧА 5. Пусть функция f(x) не определена ни при одном значении x. Будет ли функция f(x) примитивно рекурсивной, частично рекурсивной?