the corresponding partial recursive function. The unbounded search operator is not definable by the rules of primitive recursion as those do not provide a mechanism for "infinite loops" (undefined values). Normal form theorem A normal form theorem due to Kleene says that for each k there are primitive recursive functions and such that for any μ-recursive function with k free variables there is an e such that . The number e is called an index or Gödel number for the function f. A consequence of this result is that any μ-recursive function can be defined using a single instance of the μ operator applied to a (total) primitive recursive function. Minsky observes the defined above is in essence the μ-recursive equivalent of the universal Turing machine: 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 x1, ..., xn is abbreviated as x: Constant function: Kleene uses " C(x) = q " and Boolos-Burgess-Jeffrey (2002) (B-B-J) use the abbreviation " constn( x) = n ": e.g. C ( r, s, t, u, v, w, x ) = 13 e.g. const13 ( 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 =def a', where 1 =def 0', 2 =def 0 ' ', etc. Identity function: Kleene (1952) uses " U " to indicate the identity function over the variables xi; B-B-J use the identity function id over the variables x1 to xn: U( x ) = id( x ) = xi e.g. U = id ( r, s, t, u, v, w, x ) = t Composition (Substitution) operator: Kleene uses a bold-face S (not to be confused with his S for "successor" ! ). The superscript "m" refers to the mth of function "fm", whereas the subscript "n" refers to the nth variable "xn": If we are given h( x )= g( f1(x), ... , fm(x) ) h(x) = S(g, f1, ... , fm ) In a similar manner, but without the sub- and superscripts, B-B-J write: h(x)= Cn[g, f1 ,..., fm](x) Primitive Recursion: Kleene