遞歸可列舉集合

遞歸可列舉集合（英語：Recursively enumerable set）是可計算性理論或更狹義的遞歸論中的一個概念。可數集合S被稱為是遞歸可列舉、計算可列舉的、半可判定的或可證明的，如果

• 存在一個演算法，只有當輸入是S中的元素時，演算法才會中止。

或者等價的說，

• 存在一個演算法，可以將S中的成員列舉出來。也就是說該演算法的輸出就是 S 的成員列表: s₁, s₂, s₃, ... 如果需要它可以永遠執行下去。

包含所有可遞歸列舉集合的複雜性類別是 RE。

共同的編程意義會暗示出如何轉換一種演算法到等價的另一種演算法。第一種情況說明了為什麼有時說半可判定的，而第二種情況說明了為什麼叫計算可列舉的。

定義

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

$f(x) = \left\{\begin{matrix} 0 &\mbox{if}\ x \in S \\ \mbox{undef/does not halt}\ &\mbox{if}\ x \notin S \end{matrix}\right.$

換句話說，$S$ 是 $f$ 的域:

$\mathrm{dom}(f) = S$

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

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

等價定義

可數集合 $S$ 被叫做遞歸可列舉的，如果存在着一個偏可計算函數 $f :\subseteq \mathbb{N} \to S$，使得 $S$ 是 $f$ 的值域:

$\mathrm{rng}(f) = S$

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

註解

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

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

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

例子

• 所有遞歸集合都是遞歸可列舉的，但不是所有遞歸可列舉集合都是遞歸的。
• 遞歸可列舉語言是在形式語言的字母表上所有可能詞的集合中的遞歸可列舉集合。
• Matiyasevich 定理聲稱所有的遞歸可列舉集合都是丟番圖集合。
• 簡單集合是遞歸可列舉的但不是遞歸的。
• 創造集合是遞歸可列舉的但不是遞歸的。
• 生產集合不是遞歸可列舉的。
• 對於偏可計算函數 $\phi$的哥德爾數$i$，則集合 $\{\langle i,x \rangle | \phi_i(x) \downarrow\}$ (帶有 $\langle i,x \rangle$ 康拖爾配對函數) 是遞歸可列舉的。這個集合編碼了停機問題，因為它描述了每個圖靈機停機的輸入參數。
• 給定一個偏可計算函數$\phi$的哥德爾數$x$，則集合 $\lbrace \left \langle x, y, z \right \rangle | \phi_x(y)=z \rbrace$ 是遞歸可列舉的。這個集合編碼判定一個函數值的問題。

性質

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

參照

• Rogers, H. The Theory of Recursive Functions and Effective Computability, MIT Press. ISBN 0-262-68052-1; ISBN 0-07-053522-1.
• Soare, R. Recursively enumerable sets and degrees. Perspectives in Mathematical Logic. Springer-Verlag, Berlin, 1987. ISBN 3-540-15299-7.
• Soare, Robert I. Recursively enumerable sets and degrees. Bull. Amer. Math. Soc. 84 (1978), no. 6, 1149–1181.