Операция примитивной рекурсии

Пусть задана функция g и функция .

Определение. Говорят, что функция получена из функциий g и с помощью операции примитивной рекурсии, если выполняются следующие равенства:

.

Это опред-е имеет смысл, когда n≠0, при этом запис-ся:

или сокращенно, f=R(g,h), где R–означает операцию примитивной рекурсии.

В случае, когда n=0 операция примитивной рекурсии примет вид: φ(0)= ,

и обозначается:φ=R(