Т. А. Сливина математическая логика и теория алгоритмов

2. Схема примитивной рекурсии.
Пусть имеется две функции (х₂,х₃,...,х_п) и , (n > l). Рассмотрим новую функцию, которая удовлетворяет следующим равенствам:
(1)

Отметим, что функция зависит от п-1 аргументов, функция от n+1 аргументов, а функция f – от п аргументов.

Если функция получается из функций и с помощью равенств (1), то говорят, что функция f получена из функций и по схеме примитивной рекурсии.
Если функции и интуитивно вычислимы, то будет интуитивно вычислима и функция f. Действительно, пусть a₁, а₂, ..., а_п – набор значений аргументов х₁, х₂, ..., х_п. Тогда последовательно находим


,
,
и т.д.

Очевидно, что если функции и всюду определены, то будет всюду определена и функция f.

Рассмотрим примеры получения функций по схеме примитивной рекурсии.
Пример 1. Пусть функция f(y,x) задана равенствами:
f(0,x) = x,
f(y+1,x) = f(y,x) + 1.
Здесь функция , а .
Вычислим значение функции f(y,х) при у = 5, х = 2.
Т.к. f(0,2) = (2) = 2 , то из второго равенства последовательно имеем:







Нетрудно показать, что . Действительно, . Полагая в этом равенстве у = 0, получим f(z, х) = f(0, х)+z или f(z, х) = x+z.
Пример 2. Пусть функция f(y, x) задана равенствами:
f(0,x) = 0,
f(y+1,x) = f(y,x) + x.
Здесь , .
Вычислим значение функции f(у, х) при у = 2, х = 2. Так как f(0,x) = , то f(0,2) = 0 , а значения f(1,2) и f(2,2) находим последовательно:
,
.
Легко показать, что в этом примере f(y, x) = ху. Действительно, f(y + z, x) = f(y, x) + zх. Полагая в этом равенстве у = 0, получим f(z, х) = f(0, х) + zх или f(z, х) = zх.