μ-recursive function

μ-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.

Contents

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 n\, and every k\,:
    f(x_1,\ldots,x_k) = n\,.
    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:
    S(x) \stackrel{\mathrm{def}}{=}  f(x) = x + 1\,
  3. Projection function P_i^k (also called the Identity function I_i^k): For all natural numbers i, k\, such that 1 \le i \le k:
    P_i^k \stackrel{\mathrm{def}}{=} f(x_1,\ldots,x_k) = x_i.
  4. Composition operator \circ\, (also called the substitution operator): Given an m-ary function h(x_1,\ldots,x_m)\, and m k-ary functions g_1(x_1,\ldots,x_k),\ldots,g_m(x_1,\ldots, x_k):
    h \circ (g_1, \ldots, g_m) \stackrel{\mathrm{def}}{=} f(x_1,\ldots,x_k) = h(g_1(x_1,\ldots,x_k),\ldots,g_m(x_1,\ldots,x_k))\,.
  5. Primitive recursion operator \rho\,: Given the k-ary function g(x_1,\ldots,x_k)\, and k+2 -ary function h(y,z,x_1,\ldots,x_k)\,:
    \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 \mu\,: Given a (k+1)-ary total function f(y, x_1, \ldots, x_k)\,:
    \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 \simeq can be 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 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.

Minsky (1967) observes (as does Boolos-Burgess-Jeffrey (2002) pp. 94–95) that the U defined above is in essence the μ-recursive equivalent of the universal Turing machine:

To construct U is to write down the definition of a general-recursive function U(n, x) that correctly interprets the number n and computes the appropriate function of x. to construct U directly would involve essentially the same amount of effort, and essentially the same ideas, as we have invested in constructing the universal Turing machine. (italics in original, Minsky (1967) p. 189)

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 we will abbreviate the string of parameters x1, ..., xn as x:

  • Constant function: Kleene uses " Cqn(x) = q " and Boolos-Burgess-Jeffry (2002) (B-B-J) use the abbreviation " constn( x) = n ":
e.g. C137 ( 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 " Uin " to indicate the identity function over the variables xi; B-B-J use the identity function idin over the variables x1 to xn:
Uin( x ) = idin( x ) = xi
e.g. U37 = id37 ( r, s, t, u, v, w, x ) = t
  • Composition (Substitution) operator: Kleene uses a bold-face Snm (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) = Smn(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 uses the symbol " Rn(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(x,y),x )
Example: primitive recursion definition of a + b:
  • base step: f( 0, a ) = a = U11(a)
  • induction step: f( b' , a ) = ( f ( b, a ) )' = g( b, f( b, a), a ) = g( b, c, a ) = c' = S(U23( b, c, a )
R2 { U11(a), S [ (U23( b, c, a ) ] }
Pr{ U11(a), S[ (U23( 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 starting with 3 initial functions

  1. S(a) = a'
  2. U11(a) = a
  3. U23( b, c, a ) = c
  4. g(b, c, a) = S(U23( b, c, a )) = c'
  5. base step: h( 0, a ) = U11(a)
induction step: h( b', a ) = g( b, h( b, a ), a )

He arrives at:

a+b = R2[ U11, S13(S, U23) ]

Examples

See also

External links

References

  • Stephen Kleene (1952) Introduction to Metamathematics. Walters-Noordhoff & North-Holland, with corrections (6th imprint 1971); Tenth impression 1991, ISBN 0-7204-2103-9.
  • Soare, R. Recursively enumerable sets and degrees. Springer-Verlag 1987.
  • Marvin L. Minsky (1967), Computation: Finite and Infinite Machines, Prentice-Hall, Inc. Englewood Cliffs, N.J.
On pages 210-215 Minsky shows how to create the μ-operator using the register machine model, thus demonstrating its equivalence to the general recursive functions.

Wikimedia Foundation. 2010.

Look at other dictionaries:

  • Recursive function — may refer to: Recursion (computer science), a procedure or subroutine, implemented in a programming language, whose implementation references itself A total computable function, a function which is defined for all possible inputs See also μ… …   Wikipedia

  • recursive function — ▪ mathematics       in logic and mathematics, a type of function or expression predicating some concept or property of one or more variables, which is specified by a procedure that yields values or instances of that function by repeatedly… …   Universalium

  • recursive function — noun a) Any function whose value may be obtained using a finite number of operations using a precisely specified algorithm b) Any function that uses recursion and can call itself until a certain condition is met …   Wiktionary

  • Primitive recursive function — The primitive recursive functions are defined using primitive recursion and composition as central operations and are a strict subset of the recursive functions (recursive functions are also known as computable functions). The term was coined by… …   Wikipedia

  • Μ-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 μ… …   Wikipedia

  • Non-recursive function — might refer to: Recursion (computer science): a procedure or subroutine, implemented in a programming language, whose implementation references itself μ recursive function, defined from a particular formal model of computable functions using… …   Wikipedia

  • Recursive — may refer to:*Recursion *Recursively enumerable language *Recursively enumerable set *Recursive filter *Recursive function *Recursive language *Recursive acronym *Recursive set *Primitive recursive function …   Wikipedia

  • Recursive set — In computability theory, a set of natural numbers is called recursive, computable or decidable if there is an algorithm which terminates after a finite amount of time and correctly decides whether or not a given number belongs to the set. A more… …   Wikipedia

  • recursive — A procedure that is applied once, and then applied to the result of that application, and so on. A recursive definition (definition by induction) defines the result of some operation for 0, and then the result for any number n + 1 in terms of the …   Philosophy dictionary

  • Function (mathematics) — f(x) redirects here. For the band, see f(x) (band). Graph of example function, In mathematics, a function associates one quantity, the a …   Wikipedia

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”