[113]在哥德尔之后，图灵1936年的论文和斯蒂芬·克莱尼(Stephen Kleene，阿隆佐·邱奇[Alonzo Church]的学生)进一步定义了一般递归性——比如不动点定理(FixedPoint Theorem)②和正规形理论(Normal Form Theory)③;随后，邱奇在1937年对图灵1936年的论文《论可计算数及其在判定问题上的应用》(On Computable Numbers，with an Ap-plication to the Entscheidungsproblem)的评论中表示，埃尔布朗—哥德尔一克莱尼的一般递归函数等价于图灵的通用机，以及邱奇的 λ可定义函数(Lambda definable function)。①我们或许可以说，对图灵而言，可计算或可判定的东西总是递归可枚举的，即使有些计算机科学家(如罗伯特·索阿雷)建议用可判定性和可计算性的说法代替递归性，②因为递归一词在日常使用中有多种含义。然而，这种做法会忽略递归形式—它在数学和哲学理解中发挥核心作用—的重要性。一个递归函数可能无法实现其目标，因此不能停机。在这种情况下它会在无限循环中迷失，直至耗尽计算资源，比如耗尽内存，甚至达到机器的物理疲劳上限。而通用图灵机试图规定的正是这种不可判定性，以避免这种无限循环。
第二章逻辑与偶然
141
① 皮埃尔·利维，《递归的概念，从控制论到联结主义》(Lanotion de récursivité, de la première cybernétique au connexionnisme), 见 Intellectica39,2004年2月，第126页。
② 这个理论可以简单表述为：对于每一个图灵可计算的总函数f(x),都有一个不动点 n,使 φf(n)=φn(后面我们将看到不动点的说法再次出现，如终止状态[terminal state])。
③在此我们可以借用索阿雷的总结：存在一个原始递归谓词T(e,x,y)和一个原始递归函数∪(y),对于任何一般递归函数φ(x),都有一个索引 e,使 φ(x)=U(μy T(e, x, y))。见罗伯特·索阿雷(Robert I.Soare)，《可计算性和递归》(Computability and Recursion)，见《符号逻辑简报》(Bulletin o f Symbolic Logic),2,第 3期，1996年，第 301页。