Доказать, что функции примитивно-рекурсивны F(x) = x + 2; f(x) = 10^(x∸y); f(x, y) = y ∸ (y ∸ x)

Предыдущий
вопрос Следующий
вопрос

Для начала докажем, что функция F(x) = x + 2 примитивно-рекурсивна.

Функция приращения (построенная) g(z, y) = y + 1.Функция константы h(z) = 2.Теперь можем определить функцию F(x) следующим образом:
F(0) = h(0) = 2,
F(z + 1) = g(z, F(z)) = F(z) + 1.

Таким образом, можно утверждать, что функция F(x) = x + 2 примитивно-рекурсивна.

Теперь докажем, что функция f(x) = 10^(x∸y) также примитивно-рекурсивна.

Функция константы h(z) = 10.Функция умножения g(z, y) = z × y.Функция вычитания i(z, y) = z - y.Таким образом, мы можем определить функцию f(x) следующим образом:
f(0) = h(0) = 10,
f(z + 1, y) = h(g(f(z, y), i(z, y))).

Следовательно, функция f(x) = 10^(x∸y) также примитивно-рекурсивна.

Наконец, докажем, что функция f(x, y) = y ∸ (y ∸ x) также примитивно-рекурсивна.

Функция приращения (построенная) g(z, y) = y + z.Функция декремента i(z) = z - 1.Таким образом, мы можем определить функцию f(x, y) следующим образом:
f(x, 0) = g(x, 0) = x,
f(x, z + 1) = i(f(x, i(g(z, y)))).

Таким образом, можно утверждать, что функция f(x, y) = y ∸ (y ∸ x) также примитивно-рекурсивна.