Доказательство окончено

Доказательство

ТЕОРЕМА 8.2

Доказательство окончено.

Доказательство

ТЕОРЕМА 8.1

Функция f (x ₁,..., x_{n+ 1}), задаваемая выражением

f (x ₁,..., x_{n+ 1}) = g (x ₁,..., x_n, i) - примитивно-рекурсивная функция, если g (x ₁,..., x_n, x_{n+ 1}) является примитивно-рекурсивной.

Очевидно, что функция 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_i (x ₁,..., x_n), i = 1,..., k, что на всяком наборе значений переменных лишь одна из этих функций равна 0.

Кроме того, пусть заданы примитивно-рекурсивные функции h_i (x ₁,..., x_n), i = 1,..., k.

Тогда функция f (x ₁,..., x_n), определяемая выражением:

h ₁(x ₁,..., x_n), если g ₁(x ₁,..., x_n)= 0

f (x ₁,..., x_n) = ...

h _k(x ₁,..., x_n), если g _k(x ₁,..., x_n)= 0 является примитивно-рекурсивной.

Очевидно, что f можно представить с помощью следующего выражения:

f (x ₁,..., x_n) = (h_i (x ₁,..., x_n) (g_i (x ₁,..., x_n)).

Заметим, что примитивная рекурсивность функции
div (x, y) может быть установлена на основании теоремы 8.1 с помощью соотношения:

div (x, y) = ( (iy - x)).

Дата добавления: 2015-03-31