递归论

也称可计算性理论，数理逻辑的一个重要分支，以能行方法和判定问题为主要研究对象。

能行方法也叫能行过程或算法，是一个古老的直观概念，已有两千多年的历史。1900年D．希尔伯特所提出的二十三个著名问题中，第十问题就是要求给出一个能行方法来判定任意的刁番图方程是否有整数解(参见戴维斯-普特南-罗宾逊-马蒂亚谢维奇定理)。直到本世纪初，数学家们一直认为像刁番图方程的可解性这类关于自然数的问题肯定会有一个判定算法，因而希尔伯特第十问题并不是问是否存在这种算法，而是直截了当地要求给出一个算法。然而此后不久，许多工作就都要求对“能行性”这一古老概念进行严格刻画，20世纪30年代出现了若干种刻画能行性的方法。

1931年，K．哥德尔在证明他那著名的不完全性定理时，为了陈述“在一阶数论中数字可表示”这一概念，比较详细地讨论了原始递归函数。这方面的研究后经哥德尔本人和S．C．克利尼的发展、完善，形成部分递归函数(μ-递归函数)的理论。

1934年，哥德尔根据艾尔布朗的建议，构造了一种用以定义函数的形式系统。由于这种形式系统的公式都是等式，故称为等式系统。用等式系统定义的函数称为一般递归函数。这种方法又经S．C．克利尼发展、完善，形成一般递归函数的理论。稍后，A．丘奇在1936年也发表了一种用形式系统定义函数的方法。他所构造的形式系统称为λ演算，利用λ演算定义的函数称为λ可定义函数。同年，丘奇还给出了第一个不可判定问题的证明。同一时期，A．图灵在仔细研究人类进行计算的分解动作后，提出了广泛应用的图灵机理论，他的论文也发表在1936年。同年，E．L．波斯特也发表了一种与图灵机类似的计算模型。此外，波斯特和A．马尔科夫各自独立地从研究形式系统的判定问题的角度，各自提出了一种抽象的符号演算方法——波斯特系统和马尔科夫算法，它们也都可以用来计算函数。

丘奇、图灵和马尔科夫在提出各自的理论之后，都断言他们所定义的函数类就是直观意义下的能行可计算函数类。这个断言后来通常称为丘奇论题或丘奇-图灵论题。由于不久就证明上述各种理论都是彼此等价的，而且有些计算模型(如图灵机)与人的计算动作十分吻合，所以丘奇论题很快获得公认。上述各个理论也就汇合成为刻画能行方法、研究判定问题的理论。

由于当时人们所提出的判定问题差不多都是半可判定的，因而对判定问题的研究就往往可以归结为确定哪些递归可枚举集是递归集，哪些递归可枚举集不是递归集。因而对递归可枚举集的研究一直是古典递归论的中心问题。1944年，波斯特提出了其有深远影响的波斯特问题，使得对图灵度、特别是递归可枚举的图灵度的研究成为古典递归论的主线。50年代中期，弗里德伯格和穆契尼克各自独立地创立了优先方法(有穷损害的优先方法或称0′优先方法)，证明“存在两个不可比较的递归可枚举的图灵度”(因而它们既不是递归的，也不是T完全的)，解决了波斯特问题。60年代，申菲尔德和萨克斯又各自独立地创立了无穷损害的优先方法(0″优先方法)证明了厚性引理和稠密性定理。此后若干年中，人们用无穷损害的优先方法得到一大批关于递归可枚举集的结果。70年代，拉克朗又创立了优先方法。利用优先方法又得到一批关于递归可枚举集的性质。至今，优先方法仍是一个热门课题。

古典递归论所研究的是定义在自然数上的函数、关系和自然数子集。将上述对象加以推广，就得到各种广义递归论，其中主要是α递归和高类递归(参见广义递归论)。此外，在许多文献中，现代递归论还包括描述集合论和计算复杂性理论的一部分内容。(参见描述集合论、计算复杂性)