遞歸可枚舉集合

遞歸可枚舉集合（英語：Recursively enumerable set）是可計算性理論或更狹義的遞歸論中的一個概念。可數集合S被稱為是遞歸可枚舉、計算可枚舉的、半可判定的或可證明的，如果存在一個算法，只有當輸入是S中的元素時，算法才會中止。或者等價的説，存在一個算法，可以將S中的成員枚舉出來。也就是説該算法的輸出就是 S 的成員列表: s1, s2, s3, ... 如果需要它可以永遠運行下去。包含所有可遞歸枚舉集合的複雜性類是 RE。共同的編程意義會暗示出如何轉換一種算法到等價的另一種算法。第一種情況説明了為什麼有時説半可判定的，而第二種情況説明了為什麼叫計算可枚舉的。