递归论
递归论
recursion theory
数理逻辑的重要分支之一，研究解决问题的可行的计算方法和计算的复杂程度的一门学科。
解决某一类问题的计算方法又称算法。算法是个古老的数学概念。16世纪R.笛卡尔创造的解析几何就是用代数来解决几何问题的一种典型的算法。但数学中有一些问题长期找不到解决的算法。人们怀疑根本不存在这种算法。为了证明这一点，必须对算法给出精确的定义。20世纪30年代K.哥德尔提出了算法的一种精确定义，S.C.克林据此定义了递归函数。与此同时，A.M.图灵用图灵机（一种理论计算机）来描述算法，并且证明图灵可计算的函数与递归函数等价。图灵机使人们普遍接受了关于算法的丘奇论题：递归函数是可计算函数的精确的数学描述。
递归函数是用数理逻辑的方法定义在自然数集上的可计算函数 。如果自然数的一个 n 元集的特征函数是递归函数，就称这个集合为递归集，一个递归函数的值域，称为递归可枚举集。递归集就是算法可判定的集合。递归集都是递归可枚举的，但是存在不是递归集的递归可枚举的集合。递归论的研究使人们把一些长期未解决的问题化为非递归的递归可枚举集，从而严格证明了不存在判定这些问题的算法。这些问题称为不可判定的。
递归论进一步研究不可判定的，也就是非递归的递归可枚举集之间的复杂程度问题。1944年E.L.波斯特提出不可解度的概念。又给出了相对可计算性的构造方法。这就使人们开始对不可解度进行比较，并研究不可解度的代数结构。这方面出现了有穷损害优先方法、无穷损害优先方法等多种有力的研究手段，出现了许多有趣的研究成果。
对可计算的递归集，也可以研究其计算的复杂性，考虑图灵机上计算的时间，空间，就得到计算时间的长短计算所占空间的多少这两个复杂性。计算复杂性的研究对计算机科学的发展有很大影响和作用。