克莱尼递归定理

设 表示具有 递归函数 的 变量，其 哥德尔数 为 ，其中 (1) 通常被省略。那么，如果 是一个 偏 递归函数，则存在一个整数 使得

其中 是 Church 的 lambda 符号。这是最广为人知的克莱尼递归定理的变体。

另一个变体通过参数化推广了第一个变体，并且是递归定理的最强形式。这种形式指出，对于每个 ，存在一个 递归函数 的 变量，使得 是一个 单射，并且如果 是一个 全函数，那么对于所有 , ..., , 和 ,

递归定理的另一个较弱的变体保证了存在一个递归函数，该函数是递归泛函的不动点。