极小度(minimal degree)是递归论的基本概念之一。指一种小的不可解度。对不可解度a，如果a>0，且不存在不可解度b，使a>b>0，则称a为极小度。斯派克特(Spector，C.)最早证明了极小度的存在性。由于re度的稠密性，re度都不是极小度，但在0′之下存在极小度。极小度的个数为2个。库珀(Cooper，S.B.)证明了任何≥0′的度都是极小度的跳跃逆，即对任何b≥0′，存在极小度a，使a′=a∪0′=b。此外，所有极小度还构成了D的自同构基。

递归论又称“递归函数论”、“能行性理论”，指主要用数学方法研究“可构造性”、“能行可计算性”或“能行过程”的学科。各种递归函数本身的构造也是它研究的重要方面。它既属于数理逻辑的一个分支学科，不属于基础数学的一个分支学科。

递归论的主要内容包括原始递归函数，一般递归函数，部分递归函数，递归可枚举性，判定问题，递归不可解理理论，a可递归论，碾系理论等。

递归论的主要方法是通过对数论函数的研究，揭示能行过程的本质，从而解决许多重要的数学问题。

递归论对数论函数的研究从原始递归函数开始，进而推广为一般递归函数，并发现一般递归函数与能行可计算函数是可以相互定义的，凡是有一个计算过程或一个算法可以将函数值计算出来的函数都是一般递归函数。

递归论所研究的数论函数都有精确的数学定义，定义是以递归的方式进行的。例如，用递归定义方式定义“斐博那奇函数”如下：2

f(0)=0

f(1)=1

f(n+2)=f(n)+f(n+1)

通过上面的定义，对任意一个自然数n，f(n)恒可使用上述步骤逐步地取得。

在历史上，对于“能行过程”这一含糊的概念有过许多定义，如一般递归式、图灵机器、正规算法、有限自动机等。通过递归论的研究，发展这些定义彼此都是等价的。从这点可以看出，深入研究递归论对于弄清“能行过程”是十分关键的。

在这一领域里作出重要贡献的有希尔伯特、哥德尔、邱吉、图灵、克林尼、波斯特等人。

递归论不仅在数学基础的研究方面有极其重要的应用，而且在许多新兴的科学，尤其在电子计算机科学中愈来愈显示出它的重要性。

不可解度是递归论重要概念之一。指递归不可解的程度。在研究判定问题时，人们发现，不同的不可解的判定问题之间，不可解的程度有差别。已有几种方法去刻画这种不可解度。通常使用的是图灵(不可解)度。图灵度概念是建立在相对递归或相对可计算概念之上的。通常称部分函数f相对于部分函数g是递归的，若f由初始函数与g出发经有限次使用标准迭置、原始递归式和μ算子而得，则记为f≤Tg。由于任何判定问题通过适当的编码技术，都可化为如“x在A中么?”(A为N的某子集)这样的问题，因此任何一个判定问题都与N的某个子集有关。于是比较判定问题的不可解的程度可以归结为比较N的各个子集之间的某种关系。设A为N的子集，则下列一元全函数CA称为A的特征函数：

设N的两个子集A与B。称A图灵可化归于B，若函数CA递归于函数CB，记为A≤TB。若A≤TB，且B≤TA ，则称A与B是图灵等价的，记为A≡TB。可以证明关系“≡T”是一个等价关系。故按“≡T”可把N的所有子集加以分类，而每个等价类称为一个图灵度。具体地说，令A⊆N，则含有A的等价类dT(A)={B|B≡TA}称为A的图灵度，或简称为A的T度。从直观上看，若A≤TB，则相对于B的判定问题(即x∈B?)的不可解的程度不低于A的判定问题的不可解的程度。若A≡TB，则相对于A与B的两个判定问题的不可解性程度同样高。若A≤TB，但A≡\TB(即B≤\TA)，记为A