克萊尼遞迴定理

設 表示具有 遞迴函式 的 變數，其 哥德爾數 為 ，其中 (1) 通常被省略。那麼，如果 是一個 偏 遞迴函式，則存在一個整數 使得

其中 是 Church 的 lambda 符號。這是最廣為人知的克萊尼遞迴定理的變體。

另一個變體透過引數化推廣了第一個變體，並且是遞迴定理的最強形式。這種形式指出，對於每個 ，存在一個 遞迴函式 的 變數，使得 是一個 單射，並且如果 是一個 全函式，那麼對於所有 , ..., , 和 ,

遞迴定理的另一個較弱的變體保證了存在一個遞迴函式，該函式是遞迴泛函的不動點。