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