Mu-recursive function

In mathematical logic and computer science, the μ-recursive functions are a class of partial functions from natural numbers to natural numbers which are "computable" in an intuitive sense. In fact, in computability theory it is shown that the μ-recursive functions are precisely the functions that can be computed by Turing machines. 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 μ-recursive function is a primitive recursive function — the most famous example is the Ackermann function.

Other equivalent classes of functions are the λ-recursive functions and the functions that can be computed by Markov algorithms.

The set of all recursive functions is known as R in computational complexity theory..

Definition

The μ-recursive functions (or partial μ-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 initial functions are exactly the following functions:

For each natural number n and every k, the constant function $\lambda x_1,\ldots,x_k$ ^* is initial.
The successor function $\lambda x$ ^* is initial.
The projection function $\lambda x_1,\ldots,x_k$ ^* is an initial function, for all natural numbers $i \leq k$ .

The composition operation takes a function $h(x_1,\ldots,x_k)$ and functions $g_i(x_1,\ldots,x_l)$ for each $i \leq k$ and returns the function

h(g_1(x_1,\ldots,x_l),\ldots,g_k(x_1,\ldots,x_l))

The primitive recusion operation takes functions $g(x_1,\ldots,x_k)$ and $h(y,z,x_1,\ldots,x_k)$ and returns the unique function $f$ such that

f(0,x_1,\ldots,x_k) = g(x_1,\ldots,x_k)

f(y+1,x_1,\ldots,x_k) = h(y,f(y,x_1,\ldots,x_k),x_1,\ldots,x_k)

The μ operator takes a function $f(y,x_1,\ldots, x_k)$ and returns the function $\mu y f(y,x_1,\ldots,x_k)$ whose arguments are $x_1,\ldots,x_k$ . This function returns the smallest $y$ such that $f(y,x_1,\ldots,x_k)$ is defined and equals 0, if such a y exists, and is undefined otherwise.

The smallest class of functions including the initial functions and closed under composition and partial recursion is the class of primitive recursive functions. Each of these functions is total.

A partial μ-recursive function which uses that μ operator may not be total. The set of total μ-recursive functions is the subset of partial μ-recursive functions which are total. The strong equality operator $\simeq$ is used to compare partial μ-recursive functions. This is defined for all partial functions f and g so that

f(x_1,\ldots,x_k) \simeq g(x_1,\ldots,x_l)

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.

Equivalence with other models of computability

In the equivalence of models of computability, a parallel is drawn between Turing machines which 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 there for each k there are primitive recursive functions U(y) and $T(y,e,x_1,\ldots,x_k)$ such that for any μ-recursive function $f(x_1,\ldots,x_k)$ with k free variables there is an e such that

f(x_1,\ldots,x_k) \simeq U(\mu y\, T(y,e,x_1,\ldots,x_k))

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.

Examples

External links

Stanford Encyclopedia of Philosophy entry

References

Kleene, S.C. Introduction to metamathematics. Walters-Noordhoff & North-Holland 1991.

Soare, R. Recursively enumerable sets and degrees. Springer-Verlag 1987.

Recursion theory | Theory of computation