跳至內容

遞迴集合

本頁使用了標題或全文手工轉換
維基百科,自由的百科全書

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

定義

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

使得

換句話說,集合 S 是遞迴的,若且唯若指示函數 可計算的

例子

性質

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

參見