Примитивная рекурсия соответствует функциональному представлению статической ограниченной итерации или повторению (ср. с “for-повторением»), при которых параметр глубины рекурсии определяется статически (к началу итерации с помощью явно заданного числа). Отсюда получается, что при примитивной рекурсии рекурсивные вызовы всегда завершаются. Для приведенной выше схемы примитивной рекурсии путем развертывания получается следующее равенство:
f(x1, ..., xk, n) =h(x1, ..., xk, n-
h(x1,..., xk, n-2,
…
h(x1, ..., xk, 0, g(x1, ..., xk)) ... )).
Функцию f, специфицированную с помощью примитивной рекурсии над g и h, обозначается также через pr(g, h). При этом рг можно трактовать как функционал следующего вида:
рг: ((Nk -> N) х (Nk+2àN))à (Nk+1® N).
Функционал pr примитивной рекурсии соответствует схеме определения. Пишется
f= pr(g, h)
в качестве сокращения для приведенной выше схемы (*).
Равенство вида
g(x1, ..., Хm) = E
для определения функции g с произвольным выражением Е, которое образовано из символов функций f1, ..., fn и идентификаторов x1, ..., xn, может быть через применение композиции и проекции записано также в форме равенства между функциями:
g=F,
причем выражение F построено из композиций функций f1, ..., fn и проекций. Такая нотация ведет к стилю «функционального программирования», при котором вместо применения функций используются только композиции функций.
Схема примитивной рекурсии ведет, обращаясь к Т-вычислимым функциям, снова к Т-вычислимым функциям. Выражаясь точнее, справедливо следующее высказывание: если
g:Nk->N,
h:Nk+2àN
есть Т-вычислимые функции, то pr(g, h) тоже Т-вычислима. Формально J
это можно показать путем построения из двух Т-машин для вычисления g g и h новой Т-машины, которая вычисляет pr(g, h).
Определение множества PR примитивно рекурсивных функции как наименьшее подмножество множества {f: N” -> N : n Î N} n-местных (тотальных) функций над натуральными числами N со следующими свойствами этих подмножеств: