Editing General recursive function (section)

== Symbolism ==
A number of different symbolisms are used in the literature. An advantage to using the symbolism is a derivation of a function by "nesting" of the operators one inside the other is easier to write in a compact form. In the following the string of parameters x<sub>1</sub>, ..., x<sub>n</sub> is abbreviated as '''x''':
* ''Constant function'': Kleene uses " C{{su|b=q|p=n}}('''x''') = q " and Boolos-Burgess-Jeffrey (2002) (B-B-J) use the abbreviation " const<sub>n</sub>( '''x''') = n ": 
:: e.g. C{{su|b=13|p=7}} ( r, s, t, u, v, w, x ) = 13
:: e.g. const<sub>13</sub> ( r, s, t, u, v, w, x ) = 13

* ''Successor function'': Kleene uses x' and S for "Successor". As "successor" is considered to be primitive, most texts use the apostrophe as follows: 
:: S(a) = a +1 =<sub>def</sub> a', where 1 =<sub>def</sub>  0', 2 =<sub>def</sub> 0 ' ', etc.

* ''Identity function'': Kleene (1952) uses " U{{su|b=i|p=n}} " to indicate the identity function over the variables x<sub>i</sub>; B-B-J use the identity function id{{su|b=i|p=n}} over the variables x<sub>1</sub> to x<sub>n</sub>:
: U{{su|b=i|p=n}}( '''x''' ) = id{{su|b=i|p=n}}( '''x''' ) = x<sub>i</sub> 
: e.g. U{{su|b=3|p=7}} = id{{su|b=3|p=7}} ( r, s, t, u, v, w, x ) = t

* ''Composition (Substitution) operator'': Kleene uses a bold-face '''S'''{{su|b=n|p=m}} (not to be confused with his S for "successor" '''!''' ). The superscript "m" refers to the m<sup>th</sup> of function "f<sub>m</sub>", whereas the subscript "n" refers to the n<sup>th</sup> variable "x<sub>n</sub>":
:If we are given h( '''x''' )= g( f<sub>1</sub>('''x'''), ... , f<sub>m</sub>('''x''') )
::  h('''x''') = '''S'''{{su|b=m|p=n}}(g, f<sub>1</sub>, ... , f<sub>m</sub> )

:In a similar manner, but without the sub- and superscripts, B-B-J write: 
:: h(''x''')= Cn[g, f<sub>1</sub> ,..., f<sub>m</sub>]('''x''')

* ''Primitive Recursion'': Kleene uses the symbol " '''R'''<sup>n</sup>(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{{su|b=1|p=1}}(a)
::* induction step: f( b' , a ) = ( f ( b, a ) )' = g( b, f( b, a), a ) = g( b, c, a ) = c' = S(U{{su|b=2|p=3}}( b, c, a ))
::: R<sup>2</sup> { U{{su|b=1|p=1}}(a), S [ (U{{su|b=2|p=3}}( b, c, a ) ] }
::: Pr{ U{{su|b=1|p=1}}(a), S[ (U{{su|b=2|p=3}}( 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{{su|b=1|p=1}}(a) = a
:# U{{su|b=2|p=3}}( b, c, a ) = c
:# g(b, c, a) = S(U{{su|b=2|p=3}}( b, c, a )) = c'
:# base step: h( 0, a ) = U{{su|b=1|p=1}}(a)
:: induction step: h( b', a ) = g( b, h( b, a ), a )

He arrives at:
:: a+b = '''R'''<sup>2</sup>[ U{{su|b=1|p=1}}, '''S'''{{su|b=1|p=3}}(S, U{{su|b=2|p=3}}) ]