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