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