遞歸集合

可計算性理論中,一個自然數的子集被稱為遞歸的可計算的或具可判定性,如果我們可以構造一個演算法,使之能在有限時間內終止並判定一個給定元素是否屬於這個集合。更一般的集合的類叫做遞歸可列舉集合。這些集合包括遞歸集合,對於這種集合,只需要存在一個演算法,當某個元素位於這個集合中時,能夠在有限時間內給出正確的判定結果,但是當元素不在這個集合中時,演算法可能會永遠執行下去(但不會給出錯誤答案)。

定義

自然數的子集 S 被稱為遞歸的,如果存在一個可計算函數

 

使得

 

換句話說,集合 S 是遞歸的,當且僅當指示函數  可計算的

例子

性質

如果 是遞歸集合,則 補集是遞歸集合。 如果  是遞歸集合,則    是遞歸集合。集合 是遞歸集合,當且僅當  補集遞歸可列舉集合。一個遞歸集合在可計算函數下的原像(preimage)是遞歸集合。

參見