遞歸可枚舉關係

遞歸可枚舉關係，外文名recursively enumerable rela-tion。是集概念的一種

推廣。

遞歸可枚舉關係(recursively enumerable rela-tion)簡稱re關係.r。集概念的一種推廣.設P是n元數論關係，如果存在n+1元遞歸關係R，使得P(xxZ,...,x.,)HyRCyx,xZ〃..,,z.則稱P為n元遞歸可枚舉關係.與r。集類似地，P為n元re關係，若且唯若存在n元部分遞歸函式件，使P (xxZ...xn.-rx,xZ,...,x)十. re關係都是半可判定的，即對re關係P，只要P(xl,x2,...,x,)為真，總可在有限步內能行地判知因此，r。關係也稱為半遞歸關係.