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. To meet Wikipedias quality standards, this article or section may require cleanup. ... Computer science, or computing science, is the study of the theoretical foundations of information and computation and their implementation and application in computer systems. ... In mathematics, a partial function is a relation that associates each element of a set (sometimes called its domain) with at most one element of another (possibly the same) set, called the codomain. ... In mathematics, a natural number can mean either an element of the set {1, 2, 3, ...} (i. ... In mathematics, a natural number can mean either an element of the set {1, 2, 3, ...} (i. ... In computer science, computability theory is the branch of the theory of computation that studies which problems are computationally solvable using different models of computation. ... An artistic representation of a Turing Machine . ... In computability theory, primitive recursive functions are a class of functions which form an important building block on the way to a full formalization of computability. ... In computability theory, the Ackermann function or Ackermann-Péter function is a simple example of a computable function that is not primitive recursive. ...

Other equivalent classes of functions are the λ-recursive functions and the functions that can be computed by Markov algorithms. The lambda calculus is a formal system designed to investigate function definition, function application, and recursion. ... A Markov algorithm is a string rewriting system that uses grammar-like rules to operate on strings of symbols. ...

The set of all recursive functions is known as R in computational complexity theory.. The class of decision problems solvable by a Turing machine. ... As a branch of the theory of computation in computer science, computational complexity theory describes the scalability of algorithms, and the inherent difficulty in providing scalable algorithms for specific computational problems. ...

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. In computability theory, primitive recursive functions are a class of functions which form an important building block on the way to a full formalization of computability. ... In mathematics and computer science, a partial function from the domain X to the codomain Y is a binary relation over X and Y which associates with every element in the set X at most one element in the set Y. If a partial function associates with every element in... In computability theory, the Ackermann function or Ackermann-Péter function is a simple example of a computable function that is not primitive recursive. ...

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 Footnote|Symbolism):

• (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 In the mathematical subfield of set theory, the indicator function, or characteristic function, is a function defined on a set X which is used to indicate membership of an element in a subset A of X. Remark. ... In mathematics, a predicate is a relation. ...

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.

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 Footnote|Theorem IV. (For more background see the discussion at primitive recursive functions.) Undecidable has more than one meaning: In mathematical logic: A decision problem is undecidable if there is no known algorithm that decides it. ... In computability theory, primitive recursive functions are a class of functions which form an important building block on the way to a full formalization of computability. ...

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): In mathematics, a predicate is a relation. ... In language and logic, quantification is a construct that specifies the extent of validity of a predicate, that is the extent to which a predicate holds over a range of things. ...

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. In computability theory, the μ-operator is the operator which when applied to a given computable function f is a computable function returning the first value for which f is zero. ... This article or section may be confusing or unclear for some readers, and should be edited to rectify this. ...

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)

• (Note: 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)

The consequences with respect to algorithms: Turing may refer to: Alan Turing, a British computer scientist. ...

These results lead to two theorems with respect to algorithms: In mathematics, computing, linguistics, and related disciplines, an algorithm is a procedure (a finite set of well-defined instructions) for accomplishing some task which, given an initial state, will terminate in a defined end-state. ...

"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: In computability theory the Church-Turing thesis, Churchs thesis, Churchs conjecture or Turings thesis, named after Alonzo Church and Alan Turing, is a hypothesis about the nature of mechanical calculation devices, such as electronic computers. ...

"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. In logic, a decision problem is determining whether or not there exists a decision procedure or algorithm for a class S of questions requiring a Boolean value (i. ... In computability theory the halting problem is a decision problem which can be informally stated as follows: Given a description of a program and a finite input, decide whether the program finishes running or will run forever, given that input. ...

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)

Equivalence with other models of computability

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. In theoretical computer science a register machine is an abstract machine used to study decision problems, similar to how a Turing machine is used. ...

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). In computability theory the Church-Turing thesis, Churchs thesis, Churchs conjecture or Turings thesis, named after Alonzo Church and Alan Turing, is a hypothesis about the nature of mechanical calculation devices, such as electronic computers. ... An artistic representation of a Turing Machine . ...

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: The Turing machine is an abstract machine introduced in 1936 by Alan Turing to give a mathematically precise definition of algorithm or mechanical procedure. As such it is still widely used in theoretical computer science, especially in complexity theory and the theory of computation. ...

"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)

Footnotes

Footnote|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₂³) ]

Footnote|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: This article or section may be confusing or unclear for some readers, and should be edited to rectify this. ...

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. In the mathematical subfield of set theory, the indicator function, or characteristic function, is a function defined on a set X which is used to indicate membership of an element in a subset A of X. Remark. ...

• (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)

Examples

• Fibonacci number
• McCarthy 91 function

In mathematics, the Fibonacci numbers form a sequence defined recursively by: That is, after two starting values,each number is the sum of the two preceding numbers. ... In discrete mathematics, the McCarthy 91 function is a recursive function which returns 91 for all positive integer arguments n ≤ 101 and returns for n > 101. ...

See also

• Recursion theory
• Recursion
• Recursion (computer science)

Recursion theory, or computability theory, is a branch of mathematical logic dealing with generalizations of the notion of computable function, and with related notions such as Turing degrees and effective descriptive set theory. ... A Sierpinski triangle —a confined recursion of triangles to form a geometric lattice. ... A common method of simplification is to divide a problem into subproblems of the same type. ...

External links

• Stanford Encyclopedia of Philosophy entry

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.