Μ再帰関数
, x k ) = h ( g 1 ( x 1 , ... , x k ) , ... , g m ( x 1 , ... , x k ) ) {\displaystyle f(x_{1},\ldots ,x_{k})=h(g_{1}(x_{1},\ldots ,x_{k}),\ldots ,g_{m}(x_{1},\ldots ,x_{k}))} .
(5) 原始再帰作用素(Primitive recursion operator): 関数 g ( x 1 , ... , x k ) {\displaystyle g(x_{1},\ldots ,x_{k})} と h ( y , z , x 1 , ... , x k ) {\displaystyle h(y,z,x_{1},\ldots ,x_{k})} をとり、以下のような関数 f {\displaystyle f} を返す操作である。
f ( 0 , x 1 , ... , x k ) = g ( x 1 , ... , x k ) {\displaystyle f(0,x_{1},\ldots ,x_{k})=g(x_{1},\ldots ,x_{k})} ,
f ( y + 1 , x 1 , ... , x k ) = h ( y , f ( y , x 1 , ... , x k ) , x 1 , ... , x k ) {\displaystyle f(y+1,x_{1},\ldots ,x_{k})=h(y,f(y,x_{1},\ldots ,x_{k}),x_{1},\ldots ,x_{k})} .
, x k ) {\displaystyle f(0,x_{1},\ldots ,x_{k}),f(1,x_{1},\ldots ,x_{k}),...,f(y,x_{1},\ldots ,x_{k})} が全て値を返すとき、 f ( y , x 1 , ... , x k ) = 0 {\displaystyle f(y,x_{1},\ldots ,x_{k})=0} となるような自然数 y {\displaystyle y} があれば、そのうちの最小のものを返す。もしそのような y {\displaystyle y} がなければ、 μ y f {\displaystyle \mu yf} はそのときの引数 x 1 , ... , x k {\displaystyle x_{1},\ldots ,x_{k}} の組み合わせに対して定義されない。
部分μ再帰関数同士を比較する演算子として ≃ {\displaystyle \simeq } (strong equality)がある。部分関数 f {\displaystyle f} と g {\displaystyle g} について、
f ( x 1 , ... , x k ) ≃ g ( x 1 , ... , x l ) {\displaystyle f(x_{1},\ldots ,x_{k})\simeq g(x_{1},\ldots ,x_{l})}
が成り立つのは、任意の引数の組み合わせについて、両関数の定義が存在して値が同じであるか、さもなくばどちらも未定義である場合だけである。