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.
