General recursive function
In mathematical logic and computer science, a general recursive function, partial recursive function, or μ-recursive function is a partial function from natural numbers to natural numbers that is "computable" in an intuitive sense – as well as in a formal one. If the function is total, it is also called a total recursive function (sometimes shortened to recursive function). In computability theory, it is shown that the μ-recursive functions are precisely the functions that can be computed by Turing machines (this is one of the theorems that supports the Church–Turing thesis). The μ-recursive functions  are closely related to primitive recursive functions, and their inductive definition (below) builds upon that of the primitive recursive functions. However, not every total recursive function is a primitive recursive function—the most famous example is the Ackermann function. Other equivalent classes of functions are the functions of lambda calculus and the functions that can be computed by Markov algorithms. The subset of all "total" recursive functions with values in is known in computational complexity theory as the complexity class R. Definition. The μ-recursive functions (or general recursive functions) are partial functions that take finite tuples of natural numbers  and return a single natural number. They are the smallest class of partial functions that includes the initial functions and is closed under composition, primitive recursion, and the μ operator. The smallest class of functions including the initial functions and closed under composition and primitive recursion (i.e. without minimisation) is the class of primitive recursive functions. While all primitive recursive functions are total, this is not true of partial recursive functions; for example, the minimisation of the successor function is undefined. The primitive recursive functions are a subset of the total recursive functions, which are a subset of the partial  recursive functions. For example, the Ackermann function can be proven to be total recursive, and to be non-primitive. Primitive or "basic" functions: Operators (the domain of a function defined by an operator is the set of the values of the arguments such that every function application that must be done during the computation provides a well-defined result): Intuitively, minimisation seeks—beginning the search from 0 and proceeding upwards—the smallest argument that causes the function to return zero; if there is no such argument, or if one encounters an argument for which is not defined, then the search  never terminates, and formula_24 is not defined for the argument formula_25 While some textbooks use the μ-operator as defined here, others like demand that the μ-operator is applied to "total" functions only. Although this restricts the μ-operator as compared to the definition given here, the class of μ-recursive functions remains the same, which follows from Kleene's Normal Form Theorem (see below). The only difference is, that it becomes undecidable whether a specific function definition defines a μ-recursive function, as it is undecidable whether a computable (i.e. μ-recursive) function is total. The "strong equality  operator formula_26 can be used to compare partial μ-recursive functions. This is defined for all partial functions f" and "g" so that holds if and only if for any choice of arguments either both functions are defined and their values are equal or both functions are undefined. Examples. Examples not involving the minimization operator can be found at Primitive recursive function#Examples. The following examples are intended just to demonstrate the use of the minimization operator; they could also be defined without it, albeit in a more complicated way, since they are all primitive recursive. The following examples define general  recursive functions that are not primitive recursive; hence they cannot avoid using the minimization operator. Total recursive function. A general recursive function is called total recursive function if it is defined for every input, or, equivalently, if it can be computed by a total Turing machine. There is no way to computably tell if a given general recursive function is total - see "Halting problem". Equivalence with other models of computability. In the equivalence of models of computability, a parallel is drawn between Turing machines that do not terminate for certain inputs and an undefined result for that input in  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 formula_28 and formula_29 such that for any μ-recursive function formula_30 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 formula_32 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 x, ..., x is abbreviated as x: "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 He arrives at: