uses the symbol " Rn(base step, induction step) " where n indicates the number of variables, B-B-J use " Pr(base step, induction step)(x)". Given: base step: h( 0, x )= f( x ), and induction step: h( y+1, x ) = g( y, h(y, x),x ) Example: primitive recursion definition of a + b: base step: f( 0, a ) = a = U(a) induction step: f( b' , a ) = ( f ( b, a ) )' = g( b, f( b, a), a ) = g( b, c, a ) = c' = S(U( b, c, a )) R2 { U(a), S [ (U( b, c, a ) ] } Pr{ U(a), S[ (U( b, c, a ) ] } Example: Kleene gives an example of how to perform the recursive derivation of f(b, a) = b + a (notice reversal of variables a and b). He starts with 3 initial functions S(a) = a' U(a) = a U( b, c, a ) = c g(b, c, a) = S(U( b, c, a )) = c' base step: h( 0, a ) = U(a) induction step: h( b', a ) = g( b, h( b, a ), a ) He arrives at: a+b = R2[ U, S'(S, U) ] Examples Fibonacci number McCarthy 91 function See also Recursion theory Recursion Recursion (computer science) References On pages 210-215 Minsky shows how to create the μ-operator using the register machine model, thus demonstrating its equivalence to the general recursive functions. External links Stanford Encyclopedia of Philosophy entry A compiler for transforming a recursive function into an equivalent Turing machine Computability theory Theory of computation ru:Рекурсивная функция (теория вычислимости)#Частично рекурсивная функция