μ-recursive function

From Wikipedia, the free encyclopedia

This article or section may contain too much repetition. Please help improve this article, or discuss the issue on its talk page. Editing help is available. (March 2008)

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 1 Definition 2 The problem of decidability 2.1 The consequences with respect to algorithms 3 Equivalence with other models of computability 4 Normal form theorem 5 Footnotes 5.1 Symbolism 5.2 Kleene Theorem IV 6 Examples 7 See also 8 External links 9 References

[edit] 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. defined by use of the first five functions) is the class of primitive recursive functions. All primitive recursive functions are total functions. The sixth or "μ operator" is required because not all total functions that can be calculated can be done so with only the five primitive recursive functions (e.g. the Ackermann function ). In these instances the μ operator terminates the calculation. It serves as an unbounded search operator, unbounded but yet (by definition of a total function) shown by some means (e.g. an induction proof) to eventually produce a number and terminate the calculation.

However, if the unbounded μ operator itself is partial — that is, some numbers exist for which it fails to return a number — the function that makes use of it will also be a partial function — undefined for some numbers. In these instances, because it is unbounded, the μ operator will search forever, never terminating the calculation by producing a number. (Some algorithms may employ a u-operator that can produce the symbols "u" indicating "undecided" and thereby terminate the calculation (cf Kleene (1952) pp. 328ff)). Said another way: A partial μ-recursive function which uses a partial μ operator may not be total. The set of total μ-recursive functions is the subset of partial μ-recursive functions which are total.

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:

  .

  Sometimes the constant is generated by repeated use of the successor function and the object called the "initial object 0 (zero)" (Kleene (1952) p.

• (2) Successor function S: The successive passage "from an object already generated to another object n+1 or n' (the successor of n)" (ibid).

  S(x) ≡_def f(x) = x' = x +1

• (3) Projection function P_i^k (also called the Identity function I_i^k ): For all natural numbers i such that :

  P_i^k =_def .

• (4) Composition operator: Composition, also called substitution takes a function and functions for each i with and returns the function which maps x₁, ... x_k to

  .

• (5) Primitive recursion operator: Takes functions and and returns the unique function f such that

  ,

  .

• (6) μ operator: The μ operator takes a function and returns the function whose arguments are x₁ , . . ., x_k . The function f is either a number-theoretic function from natural numbers { 0, 1, ... n } to natural numbers { 0, 1, ... n } or a representing function that operates on a predicate (with output { t, f } ) to yield { 0, 1 }.

  In either case: this function μy f returns the smallest natural number y such that f(0,x₁,x₂,...,x_k), f(1,x₁,x₂,...,x_k), ..., f(y,x₁,x₂,...,x_k) are all defined and f(y,x₁,x₂,...,x_k) = 0, if such an y exists; if no such y exists, then μy f is not defined for the particular arguments x₁,...,x_k.

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

[edit] The problem of decidability

The question immediately arises: Suppose the algorithm we design to calculate our numbers is not terminating? Do we or do we not have a "calculable" function? How would we decide this? Kleene describes it this way:

We start with the notion of an "effectively decidable predicate":

εyR(x,y) = IF (Ey)R(x,y) THEN ε ="least y such that R(x,y)" ELSE 0.

Kleene proposes that "we can search through the propositions R(x,0), R(x,1), R(x,2), ... in succession, looking for one that is true, as far as we please:

But if x is such that NOT_(Ey)R(x,y), we shall never learn this by persisting in the search, which will remain forever uncompleted. The completion of the examination of all aleph₀ propostions, which the classical definition envisages, is impossible for a human computer.

But, for some choices of R(x,y) the function εyR(x,y) may nevertheless be effectively calculable ... because of some other procedure...[which] is effective.

[Thus] the function εyR(x,y) is effectively calculable, if and only if the predicate (Ey)R(x,y) is effectively decidable. (Kleene pp. 317-318)

So how do we determine if our misbehaving algorithm is "decidable"? Can we submit it to a "termination-analysis" algorithm that will render "the decision" YES or NO? The proof why the answer is "undecidable" is complex because of all the definitions. The point of it is that Kleene can enumerate all the total recursive functions and show, by Cantor's diagonal method, that more functions exist than can be defined recursively. An adventureous reader may want to read Theorem IV below. (For more background see the discussion at primitive recursive functions.)

Theorem IV (the enumeration theorem)

We can enumerate (assign a number to) all the (total) recursive functions.

The following is a verbal account of Kleene's theorem. In the following we abbreviate the string of n parameters (number-variables) x₁, ... x_n as x. A predicate function yields { true, false } rather than a number. The quantifier expressions are Kleene's 'intuitive symbolism' (cf p. 225):

For example: (y)R(y) means "for all y R(y) is true, and (Ey)R(y) means "there exists a unique y such that R(y) is true."

We start with a total μ-recursive function R(x, y). The fact that R is total μ-recursive means it is defined by a "system" (a sequence) of primitive recursive operators D and a mu operator E. Kleene calls this "system" F. F is equipped with the variables x that take place of the numbers we will use as parameters. For this F, Kleene shows how we can calculate a number f, the Gödel number of the system of equations F with the variables x embedded in the number.

Suppose we have some natural numbers that we want to plug into the various x of our recursive function R. As our function R is total recursive we should be able to plug any numbers into the various x_i and have our function R(x, y) yield a single number y as output (by the definition of a total μ-recursive function). This y represents the "the deduction Y" from F, given the parameters x.

Ditto for a new predicate T_n that Kleene defines in terms of (i) the Gödel number f of "system of equations" F, (ii) system F's parameters x, and (iii) a final number y that should pop out after we choose some natural numbers to plug into the x and apply function T_n to f, x, and y:

(y)R(x, y) ≡ (Ey) T_n (f, x, y)

Kleene shows that, given an f and an instance of parameters x, the predicate T_n is true for at most one Gödel number y. In other words, we don't expect that if f as the legitimate Gödel number of a system of equations F, that an single instance of parameters T_n would yield two or three numbers e.g. y₁, y₂, y₃, or a different number y than we would get from R.

From these considerations he derives the following "enumeration theorem":

Theorem IV: For each n ≥ 0: Given any general recursive predicate R(x, y), numbers f and g exist such that:

(Ey)R( x, y) ≡ (Ey)T_n(f, x, y)

(y)R( x, y) ≡ (y) NOT_(T_n)(g, x, y)

where T_n(z, x, y) is the particular primitive recursive predicate defined above.... (p. 281)

Kleene describes the theorem this way:

Briefly, (Ey)T_n(f, x, y) 'enumerates' the predicates of the form (Ey)R( x, y) with a general recursive R. Similarly, (y) NOT_(T_n)(g, x, y) enumerates the predicates of the form (y)R( x, y). (p. 282)

Theorem V

There are more number-theoretic predicates than recursive functions.

Kleene now reduces the problem from a sequence of variables x a single variable x that will accept any natural number. By use of Cantor's diagonal argument, Kleene's Theorem V shows that there is a problem that appears when we let x = Gödel number f in the first formula and x = Gödel number g in the second formula. In other words, for its "parameter" x, we plug in the "system" F's very own Gödel number f. There is nothing that says we cannot do this; if the function Y (repesented by Gödel number y) is a total recursive function derivable from F (represented by Gödel number f) we should be able to plug in any number into x and satisfy the equation, but we cannot:

(Ey)R( f, y ) ≠ (y) NOT_(T₁)(f, f, y)

(y)R( g, y ) ≠ (Ey) T₁(g, g, y)

Kleene explains the proof this way:

The proof ... amounts simply to this: (Ey)T₁(z, x, y) for z = 0, 1, 2, ... is an enumeration (with repetitions) of all predicates of the form (Ey)R(x,y) with R recursive. By Cantor's diagonal method, NOT_(Ey)T₁(x, x, y) is a predicate not in the enumeration. The latter is equivalent to (y)NOT_T₁ (x, x, y).

From the eunumerability of all systems E of equations, we can conclude without the present theory that the general recursive predicates are enumerable... hence by Cantor's results ... they cannot constitute all number-theoretic predicates. (p. 283)

(This is analogous to what happens to a universal Turing machine running a generalized decision-program to answer the question "For all programs, 'Will this program enter a pernicious "circle"?'" When the machine arrives at its own number to test (i.e. the number representing the UTM + the number of the program: "For all programs, 'Will this program enter a pernicious 'circle'?" ) it cannot "answer YES" because by definition/premise it is circle-free (and designed to answer the question FOR ALL instances). So to test for NO — "When I test my own number, will I end in a circle?" — it must test its own behavior. So it starts from scratch and tests all the numbers up to and including itself (time #2). Once there, it must retest itself again (time #3 — why is this time any different than time #2), etc. It has entered an infinitely regressive "circle" and never answers the question. (Turing's 1936 proof reprinted in The Undecidable, page 133)

[edit] The consequences with respect to algorithms

These results lead to two theorems with respect to algorithms:

Theorem XII: There is no decision procedure (or algorithm) for either of the predicates (y)NOT_T₁ (x, x, y) or (Ey)T₁(x, x, y). (p. 301)

Theorem XIII (Part 1): There is no correct and complete formal system for the predicate:

(y)NOT_T₁(x, x, y). (A generalized form of Gödel's Theorem, Kleene 1943.) (p. 302)

And these lead to the following conclusions if we accept Church's thesis:

Hence any algorithm which will lead to the number μyT₁(x, x, y) for every x such that (Ey)T₁(x, x, y) cannot terminate for every x (using Thesis I [Church's Thesis]). (p. 324)

Hence, there is no algorithm for deciding, given x, whether μyT₁ (x, x, y) is defined or not. (p.325)

Thus we are confronted with the problem of undecidability — the halting problem. There is no testing-algorithm we can build that will tell us "YES" = 0 or "NO" = 1, for all algorithms starting with Gödel number 1, whether each algorithm will terminate or not. When the testing algorithm arrives at its own number, it will not terminate.

Kleene's answer to Hilbert's 2nd Problem

Church's thesis, by supplying a precise delimitation of 'all effectively calculable functions' make it possble to prove, for certain predicates R(x, y) e.g. T₁(x, x, y) ( Theorem XII ), that there is no uniform method of solving the problem whether or not (Ey)R(x,y). Thereby Brouwer's argument, that Hilbert's belief in the solvability of every mathematical problem is unproven, is now strengthened to an actual disproof, when solvability is taken to mean uniform solvability and Church's thesis is accepted. (boldface added, p. 318)

[edit] Equivalence with other models of computability

Please help improve this section by expanding it. Further information might be found on the talk page or at requests for expansion.

Kleene's proof of the equivalence of "computable functions by Turing machine" to "partial functions" that are arrived by "use of the primitive recursive operators and the u-operator" can be expressed in its final form as a Theorem:

Theorem XXX ( = Theorems XXVIII + XXIX). The following classes of partial functions are coextensive, i.e. have the same members: 9a) the partial recursive functions, (b) the computable [by some machine] functions, (c) the 1/1 [Turing machine reduced to one-way tape, 1-symbol ] functions. Similarly with l completely defined assumed functions Ψ. (Kleene p. 376)

To prove formal equivalence, Kleene is required to prove the two parts of this Theorem XXX. Theorem XXVIII (Kleene pp. 363 ff) proceeds by showing how to convert the five primitive-recursive operators and the μ-operator to their Turing equivalents so a Turing machine can emulate an algorithm using the recursion operators. Theorem XXIX (Kleene pp 373-376) proceeds by arithematizing the actions of a Turing machine and showing that this number can be arrived at by use of various primitive recursive functions and a u-operator at the end to terminate the calculation.

Equivalence of various computational models (e.g. register machines) usually proceed with a demonstration that the machine is equivalent to a Turing machine (i.e. two proofs are required — for all instances (i) the machine-in-question implies a Turing machine AND (ii) a Turing machine implies the machine-in-question.

As noted above: 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).

[edit] Normal form theorem

A normal form theorem due to Kleene says that there 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 (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)

[edit] Footnotes

[edit] 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 x₁, ..., x_n as x:

• Constant function: Kleene uses " C_qⁿ(x) = q " and Boolos-Burgess-Jeffry (2002) (B-B-J) use the abbreviation " const_n( x) = n ":

e.g. C₁₃⁷ ( r, s, t, u, v, w, x ) = 13

e.g. const₁₃ ( 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_iⁿ " to indicate the identity function over the variables x_i; B-B-J use the identity function id_iⁿ over the variables x₁ to x_n:

U_iⁿ( x ) = id_iⁿ( x ) = x_i

e.g. U₃⁷ = id₃⁷ ( r, s, t, u, v, w, x ) = t

• Composition (Substitution) operator: Kleene uses a bold-face S_n^m (not to be confused with his S for "successor" ! ). The superscript "m" refers to the m^th of function "f_m", whereas the subscript "n" refers to the n^th variable "x_n":

If we are given h( x )= g( f₁(x), ... , f_m(x) )

h(x) = S_mⁿ(g, f₁, ... , f_m )

In a similar manner, but without the sub- and superscripts, B-B-J write:

h(x')= Cn[g, f₁ ,..., f_m](x)

• Primitive Recursion: Kleene uses the symbol " Rⁿ(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 = U₁¹(a)
• induction step: f( b' , a ) = ( f ( b, a ) )' = g( b, f( b, a), a ) = g( b, c, a ) = c' = S(U₂³( b, c, a )

R² { U₁¹(a), S [ (U₂³( b, c, a ) ] }

Pr{ U₁¹(a), S[ (U₂³( 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. U₁¹(a) = a
3. U₂³( b, c, a ) = c
4. g(b, c, a) = S(U₂³( b, c, a )) = c'
5. base step: h( 0, a ) = U₁¹(a)

induction step: h( b', a ) = g( b, h( b, a ), a )

He arrives at:

a+b = R²[ U₁¹, S₁³(S, U₂³) ]

[edit] Kleene Theorem IV

Theorem IV: We can enumerate all the (total) recursive functions.

In theorem IV (p. 281) he proves that, given a recursive function R(x, y) — where x is our abbreviation for a string of n parameters (number-variables) x₁, ... x_n — there exists a Gödel number f that can satisfy a special predicate T (i.e. T is a function yielding { true, false } ). By use of this predicate he can "enumerate" (assign a number to) all the recursive functions R(x, y) in the following manner:

The definitions begin with this:

• (1) G is defined in terms of a sequence of functions (recursive operators) operating on the parameters x that make up "a deduction" of Y from Z: G(Z, x, Y)

D is the system of equations that recursively define the representing function ψ of R. The (slightly expanded) system of equations F is defined as DE, where E represents the u-operator that terminates the calcuation.

• (2) (Ey)R(x,y)≡ (EY)G(F, x, Y)

f is the Gödel number of the system of equations F. y is the Gödel number of "an entity Y" deduced from F. A second equation is defined as follows:

S_n(f, x, y)≡ { y is the Gödel number of an entity Y such that G(F, x, Y), where the subscript n of S_n indicates S has n parameters

• (3) (EY) G(F, x, Y) ≡ (Ey) S_n(f, x, y)

Equating equations (2) and the one immediately above:

• (4) (Ey)R(x,y)≡ (Ey)_n(f, x, y)

Kleene replaces S_n with a predicate T_n defined from it. The predicate means:

For given [numbers] z [and] x, T_n(z, x, y) is true for at most one [number] y. (p. 281).

Thus we see that if y is a Gödel number of the deduction Y, then T_n is true for only this one y given Gödel number z. And T_n is primitive recursive, S_n is recursive. This allows Kleene to write:

T_n (z, x, y) ≡ S_n (z, x, y) & ( t )_t<y NOT_S_n (z, x, t)

Theorem IV: For each n ≥ 0: Given any general recursive predicate R(x, y), numbers f and g exist such that:

(Ey)R( x, y) ≡ (Ey)T_n(f, x, y)

(y)R( x, y) ≡ (y) NOT_(T_n)(g, x, y)

Kleene describes the theorem this way:

Briefly, (Ey)T_n(f, x, y) 'enumerates' the predicates of the form (Ey)R( x, y) with a general recursive R. Similarly, (y) NOT_(T_n)(g, x, y) enumerates the predicates of the form (y)R( x, y). (p. 282)

[edit] Examples

• Fibonacci number
• McCarthy 91 function

[edit] See also

• Recursion theory
• Recursion
• Recursion (computer science)

[edit] External links

• Stanford Encyclopedia of Philosophy entry

[edit] 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.

• George Boolos, John Burgess, Richard Jeffrey (2002), Computability and Logic: Fourth Edition, Cambridge University Press, Cambridge, UK. Cf pp. 70-71.