Примитивно рекурсивные функции. Базисными функциями называются следующие функции: – нулевая функция; – функция следования;
Базисными функциями называются следующие функции: Оператор суперпозиции (подстановки)
Оператор примитивной рекурсии
Частична функция Пример 2. Функция сложения
Пример 3. Функция умножения
|
– нулевая функция; 
– функция следования; 
– функция выбора.
ставит в соответствие m -местной частичной функции 
и n -местным частичным функциям 
n -местную частичную функцию 
, удовлетворяющую тождеству:
ставит в соответствие n+2 -местной частичной функции 
и n -местной частичной функции 
n+1 -местную частичную функцию 
, удовлетворяющую схеме примитивной рекурсии:
называется примитивно рекурсивной (ПРФ), если существует последовательность частичных функций 
, в которой 
и всякая 
является либо базисной функцией, либо получается из предыдущих функций с помощью оператора суперпозиции 
или примитивной рекурсии 
.
является ПРФ:
является ПРФ:
