TOPICS
Search

Kleene's Recursion Theorem


Let phi_x^((k)) denote the recursive function of k variables with Gödel number x, where (1) is normally omitted. Then if g is a partial recursive function, there exists an integer e such that

 phi_e^((m))=lambdax_1,...,x_mg(e,x_1,...,x_m),

where lambda is Church's lambda notation. This is the variant most commonly known as Kleene's recursion theorem.

Another variant generalizes the first variant by parameterization, and is the strongest form of the recursion theorem. This form states that for each k, there exists a recursive function f of k+2 variables such that f is a injection and if phi_z^((k+1)) is a total function, then for all x_1, ..., x_k, and y,

 phi_(f(z,x_1,...,x_k,y)) 
 =phi_(phi_z^((k+1))(y))(f(z,x_1,...,x_k,y),x_1,...,x_k).

Yet another and weaker variant of the recursion theorem guarantees the existence of a recursive function that is a fixed point for a recursive functional.


See also

Gödel Number, Kleene's s-m-n Theorem, Recursive Function

This entry contributed by Alex Sakharov (author's link)

Explore with Wolfram|Alpha

References

Davis, M. Computability and Unsolvability. New York: Dover, 1982.Kleene, S. C. Introduction to Metamathematics. Princeton, NJ: Van Nostrand, 1964.Rogers, H. Theory of Recursive Functions and Effective Computability. Cambridge, MA: MIT Press, 1987.

Referenced on Wolfram|Alpha

Kleene's Recursion Theorem

Cite this as:

Sakharov, Alex. "Kleene's Recursion Theorem." From MathWorld--A Wolfram Web Resource, created by Eric W. Weisstein. https://mathworld.wolfram.com/KleenesRecursionTheorem.html

Subject classifications