递归论 递归论或可计算性理论是一个数理逻辑分支它起源于可计算函数和图灵度的研究它的领域增长为包括一般性的可计算性和可定义性的研究在这些领域中这门理论同证明论和能行描述集合论effective descriptive set theory有所重叠 数理逻辑中的可计算性理论家经常研究相对可计算性可归约性概念和程度结构的理论相对于计算机科学家他们研究次递归层次可行的计算和公用于可计算性理论研究的形式语言在这两个社区之间有着相当大的知识和方法上的重叠而没有明显的界限