μ-recursive Function - Definition

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 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 set of total recursive functions is a subset of the partial recursive functions and is a superset of the primitive recursive functions; functions like the Ackermann function can be proven to be total recursive, and not primitive.

The first three functions are called the "initial" or "basic" functions: (In the following the subscripting is per Kleene (1952) p. 219. For more about some of the various symbolisms found in the literature see Symbolism below.)

  1. Constant function: For each natural number and every :
    .
    Alternative definitions use compositions of the successor function and use a zero function, that always returns zero, in place of the constant function.
  2. Successor function S:
  3. Projection function (also called the Identity function ): For all natural numbers such that :
    .
  4. Composition operator (also called the substitution operator): Given an m-ary function and m k-ary functions :
    .
  5. Primitive recursion operator : Given the k-ary function and k+2 -ary function :
    \begin{align} \rho(g, h) &\stackrel{\mathrm{def}}{=} f(y, x_1,\ldots, x_k) \quad {\rm where} \\ 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)\,\end{align}.
  6. Minimisation operator : Given a (k+1)-ary total function :
    \begin{align} \mu(f)(x_1, \ldots, x_k) = z &\stackrel{\mathrm{def}}{\iff}\ \exists y_0, \ldots, y_z \quad {\rm such\ that}\\ y_i &= f(i, x_1, \ldots, x_k) \quad {\rm for}\ i=0, \ldots, z \\ y_i &> 0 \quad{\rm for}\ i=0, \ldots, z-1 \\ y_z &= 0 \end{align}
    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, the search never terminates.

The strong equality operator 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.

Read more about this topic:  μ-recursive Function

Famous quotes containing the word definition:

    “It’s a rare parent who can see his or her child clearly and objectively. At a school board meeting I attended . . . the only definition of a gifted child on which everyone in the audience could agree was “mine.””
    —Jane Adams (20th century)

    “The physicians say, they are not materialists; but they are:MSpirit is matter reduced to an extreme thinness: O so thin!—But the definition of spiritual should be, that which is its own evidence. What notions do they attach to love! what to religion! One would not willingly pronounce these words in their hearing, and give them the occasion to profane them.”
    —Ralph Waldo Emerson (1803–1882)

    “Beauty, like all other qualities presented to human experience, is relative; and the definition of it becomes unmeaning and useless in proportion to its abstractness. To define beauty not in the most abstract, but in the most concrete terms possible, not to find a universal formula for it, but the formula which expresses most adequately this or that special manifestation of it, is the aim of the true student of aesthetics.”
    —Walter Pater (1839–1894)