当存在一个以φ结尾的有限数论函数序列 $\varnothing _ { 1 }$ $\varnothing _ { 2 }$ ,$\scriptstyle \varnothing _ { \mathfrak { n } }$ ，且每个函数 $\rho _ { \mathrm { k } }$ 都递归地由前面两个函数定义，或可通过替换从前面的任意函数中得出，或是一个常数，或是后继函数x+1，则称这个数论函数φ是递归的。①
我们或许可以把这种说法简化为F(x)=kF(x—1)的形式，这个函数返回到它自身和前一个函数的结果上。正因此，我们可以把它与哥德尔对冈瑟提出的反思逻辑的兴趣联系起来。1934年哥德尔在他的论文《论形式数学的不可判定命题》中提出了一般递归函数。他(通过与法国逻辑学家雅克·埃尔布朗[Jacques Herbrand]的通信)注意到，他[112]早先的递归函数不能包括所有有效的可运算函数。在第9节“一般递归函数”中，哥德尔对递归函数做了类似定义：
我们或许可以把这个概念定义如下：如果φ表示某一未知函数，而ψ，…ψ是已知的函数，若ψ和φ能以最一般的方式相互替代，且替换后的某些表达式不变，且如果结果函数方程组对于φ有唯一解，则ψ是递归函数。②
这第二个定义更抽象，因为它涉及两个函数，复杂性程度更高，但它也突出了递归理论的三个主要观点：1.可以用递归函数表示的东西是递归可枚举的，即可计算的；2.它从一个简单函数开始，以达到一个复杂函数，这通常可以用涌现现象说明；3.为了得出已知函数，它首先假定了未知函数，也就是说虽然黑箱不能明确地被知晓，却可以被其他已知函数替代，后者的递归运算能得出与未知函数相同的结果。①哥德尔给出的这个例子可能有助于我们的理解：
140
递归与偶然
① 哥德尔，《全集》，第1卷，所罗门·费弗曼等人编，牛津：Claren-don,2001年，第159页。
② 同上，第268页。