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