Функция называется примитивной рекурсией, если она получается из простейших путем конечного числа применений операций подстановки и примитивной рекурсии.
Утв.1
Все ПРФ являются всюду определенными.
Утв.2
Операции подстановки и ПР, примененные к всюду примененным функциям, в результате дают всюду определенную функцию.
Th Робинсона
q(x) = x – [sq2]^2
Все одноместные ПРФ и только они могут быть получены из функции s(x), q(x) при помощи конечного числа применений операции сложения, подстановки итерации.
Для одноместных функций подстановка не предусмотрена.
