递归集

递归集是递归论用语。令A?Nn，如果A的特征函数CA(x1，…，xn)是μ-递归函数，则称A为递归集。递归集是具有能行可计算的自然数集。设A为自然数集合，若其特征函数CA是递归函数，则称A为递归集。对递归集合A，为了判定某个自然数n是否属于A，只要计算其特征函数CA在n处的值CA(n)即可。由于CA的递归性，上述过程可能行地完成，从而n是否属于A是能行可判定的。?，N都是递归集，而且任何有穷集也都是递归的。此外，递归集类关于集合的交、并、补运算都是封闭的。[1]