Kleene's Recursion Theorem

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

where  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 , there exists a recursive function  of  variables such that  is a injection and if  is a total function, then for all , ..., , and ,

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.

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.