Я знаю определение примитивной рекурсивной функции: функция, которая может быть определена конечным количеством операций рекурсии из исходных функций (нуль, приращение и проекция).
И функция, определенная как рекурсия из примитивно-рекурсивной функции также является примитивно-рекурсивной.
Тогда есть теорема о композиции: для функции f (x1 ... xk) и функций g1 (x1 ... xn), g2 (x1 .. .xn) ... gk (x1 ... xn), функция: h (x1 ... xn) = f (g1 (x1 ... xn), g2 (x1 ... xn) ... gk (x1 ... xn)) полностью вычислимо, если f и g1 ... gk также полностью вычислимы.
Однако я не нашел никакого ответа на вопрос: если f и g1 ... gk примитивно-рекурсивно, тогда h также примитивно-рекурсивно?
Класс примитивно-рекурсивных функций в классе тотальных функций, поэтому я не знаю ответа, а тем более объяснения.