15-§. Структура примитино рекурсивных функций. Реализация алгоритма на машине Тьюринга

15.2. Схема примитивной рекурсии.
Пусть имеется две функции  и .
Рассмотрим новую функцию, которая удовлетворяет следующим равенствам:
(1)
Отметим, что функция  зависит от  аргументов, функция   от аргументов, а функция f – от п аргументов.
Если функция получается из функций  и  с помощью равенств (1), то говорят, что функция f получена из функций  и  по схеме примитивной рекурсии.
Если функции  и   интуитивно вычислимы, то будет интуитивно вычислима и функция . Действительно, пусть   – набор значений аргументов . Тогда последовательно находим

и т.д.
Очевидно, что если функции  и  всюду определены, то будет всюду определена и функция f.
Рассмотрим примеры получения функций по схеме примитивной рекурсии.
Пример 1. Пусть функция задана равенствами:


Здесь функция  а .
Вычислим значение функции   при у = 5, x = 2.
Т.к. то из второго равенства последовательно имеем:





Нетрудно показать, что
.
Действительно, .
Полагая в этом равенстве  , получим   или  .
Пример 2. Пусть функция  задана равенствами:
,
.
Здесь , .
Вычислим значение функции  при 
Так как , то , а значения и находим последовательно:
,
.
Легко показать, что в этом примере
Действительно, Полагая в этом равенстве  , получим  или