display | more...

In Computation Theory, the Recursion Theorem allows a turing machine T to obtain its own description <T>. So given T, we would like to construct R such that R(w) = T(<R>, w). We need some intermediate functions to do this construction. I will use a lambda calculus notation:

P = \w. \x. w
Q = \w. P w
B = \m. m (Q m)
R = \w. T (B (P T(B) w), w)
R w = T (B (P T(B) w), w)
    = T (B (T (B)), w)
    = T (T (B (Q T(B))), w)
    = T (\w. T (B (P T(B) w)), w)
    = T (R, w)
For example, if we wanted a function to recursively compute 2^n, we'd let
E = \f. \x. (if x = 0 then 1 else 2 * f(x-1))
R = \w. E (B (P E(B) w), w)
perhaps using a polymorphic representation of if-then-else statements. So anyway, to do the computation, we'd do
R 2 = E(R, 2)
    = if 2 = 0 then 1 else 2 * R(2-1)
    = 2 * R(1)
    = 2 * E(R, 1)
    = 2 * (if 1 = 0 then 1 else 2 * R(1-1))
    = 2 * 2 * R(0)
    = 2 * 2 * E(R, 0)
    = 2 * 2 * (if 0 = 0 then 1 else 2 * R(0-1))
    = 2 * 2 * 1
    = 4

The recursion theorem is actually several different theorems about recursion that give several slightly different results, and are used to justify the use of recursion in programming. All of these forms are the work of Stephen Cole Kleene.

One form of the recursion theorem states that every total recursive function σ that maps description numbers to other description numbers has a fixed point n such that φn = φσ(n), where φn denotes the partial recursive function calculated by the Turing machine corresponding to the DN n. In other words, if we modify all possible Turing machines somehow, there exists some Turing machine Mn for which the modified Turing machine Mσ(n) still computes the same function! At first, this seems impossible: we might have σ(e) produce the DN of a Turing machine that computes φe(x) + 1, for instance, and well, φ(x) + 1 is never equal to φ(x). Unless of course φ(x) is everywhere undefined, giving us a fixed point.

This theorem is useful, among other things, for showing the existence of quines, programs that can print themselves, for any Turing complete system. In the world of Turing machines, this means that, there exists a description number q such that φq is a constant function whose value is q. This may easily be seen by taking the total recursive function ψ(e, x) = e, for all e and x. Using the Smn theorem, there exists a total recursive function f such that φf(e)(x) = ψ(e, x). From the recursion theorem, f has a fixed point q. Thus, for all x:

φq(x) = φf(q)(x) = ψ(q, x) = q

A second form of the recursion theorem, stronger than the first, deals with functionals, or higher-order functions, functions that themselves operate on functions to produce other functions. This form of the theorem deals with functionals of the form F(φ;x1, ..., xn) = ψ(x1, ... xn), that is functionals that take a function φ(x1, ..., xn) and a set of n arguments, producing another function ψ. This form of the recursion theorem states that for every partial recursive functional F of this form, there exists a solution φ for this recursive definition:

F(ξ;x1, ..., xn) = ξ(x1, ..., xn)

such that φ is itself a partial recursive function. This solution can also be thought of as being a minimal one in the following sense: If we have two partial recursive functions ψ and φ, we say that ψ extends φ if the set of all ordered pairs {(x, φ(x)} is a subset of {(x, ψ(x)}. The solution φ guaranteed by this second form of the recursion theorem can also be said to be minimal in that any other possible solution ψ extends φ. Thus φ is a least fixed point of the functional F.

A third form of the recursion theorem, in some ways stronger and in some ways weaker than the second, states that if F is a functional of the form F(ξ, z, x1, ..., xn), then there exists a description number e corresponding to the function φe such that:

φe(x1, ..., xn) = F(φe; e, x1, ..., xn)

This is a stronger result than the second form because now the functional F is also permitted to depend not only upon a function φ but also on a description number corresponding to φ. It is weaker because nothing in the theorem states that this fixed point φe is a least fixed point.

Log in or register to write something here or to contact authors.