遞歸可枚舉集合

遞歸可枚舉集合（英語：Recursively enumerable set）是可計算性理論或更狹義的遞歸論中的一個概念。可數集合S被稱為是遞歸可枚舉、計算可枚舉的、半可判定的或可證明的，如果存在一個算法，只有當輸入是S中的元素時，算法才會中止。或者等價的說，存在一個算法，可以將S中的成員枚舉出來。也就是說該算法的輸出就是 S 的成員列表: s1, s2, s3, ... 如果需要它可以永遠運行下去。包含所有可遞歸枚舉集合的複雜性類是 RE。共同的編程意義會暗示出如何轉換一種算法到等價的另一種算法。第一種情況說明了為什麼有時說半可判定的，而第二種情況說明了為什麼叫計算可枚舉的。

基本介紹

• 中文名：遞歸可枚舉集合
• 外文名：Recursively enumerable set

定義

可數集合 S 是遞歸可枚舉的，如果存在一個偏可計算函式 f 使得

換句話說，S是 f的域:

(注意這是偏函式的域的兩種可能意義之一，是在遞歸論中所偏好的定義域。參見在偏函式中的討論。

集合S被成為co-遞歸可枚舉的或co-r.e.，如果S的補集是遞歸可枚舉的。

等價定義

可數集合S被叫做遞歸可枚舉的，如果存在著一個偏可計算函式 ，使得 S是 f 的值域:

f被稱為枚舉函式，因為它關聯上一個枚舉上的次序(rank)到 S 的每個元素。

註解

因為邱奇-圖靈論題聲稱可計算函式被圖靈機和其他計算模型等價的定義，我們陳述定義為

• 可數集合S被稱為遞歸可枚舉的，如果有一個圖靈機，在給定S的一個元素作為輸入的時候，總是停機，並在給定的輸入不屬於S的時候永不停機。

這也是遞歸可枚舉集合的常見定義。

例子

• 所有遞歸集合都是遞歸可枚舉的，但不是所有遞歸可枚舉集合都是遞歸的。
• 遞歸可枚舉語言是在形式語言的字母表上所有可能詞的集合中的遞歸可枚舉集合。
• Matiyasevich 定理聲稱所有丟番圖集合都是遞歸可枚舉的。
• 簡單集合是遞歸可枚舉的但不是遞歸的。
• 創造集合是遞歸可枚舉的但不是遞歸的。
• 生產集合不是遞歸可枚舉的。

對於偏可計算函式 的哥德爾數i，則集合 (帶有 康拖爾配對函式) 是遞歸可枚舉的。這個集合編碼了停機問題，因為它描述了每個圖靈機停機的輸入參數。

給定一個偏可計算函式 的哥德爾數x，則集合 是遞歸可枚舉的。這個集合編碼判定一個函式值的問題。

性質

如果A和B是遞歸可枚舉集合，則A∩B、A∪B和A×B是遞歸可枚舉集合。集合A是遞歸集合，若且唯若A和A補集二者是遞歸可枚舉集合。遞歸可枚舉集合一個可計算函式下的原像是遞歸可枚舉集合。