Computably enumerable set

In computability theory, a set S of natural numbers is called computably enumerable (c.e.), recursively enumerable (r.e.), semidecidable, partially decidable, listable, provable or Turing-recognizable if:

• There is an algorithm such that the set of input numbers for which the algorithm halts is exactly S.

Or, equivalently,

• There is an algorithm that enumerates the members of S. That means that its output is a list of all the members of S: s₁, s₂, s₃, ... . If S is infinite, this algorithm will run forever, but each element of S will be returned after a finite amount of time. Note that these elements do not have to be listed in a particular way, say from smallest to largest.

The first condition suggests why the term semidecidable is sometimes used. More precisely, if a number is in the set, one can decide this by running the algorithm, but if the number is not in the set, the algorithm can run forever, and no information is returned. A set that is "completely decidable" is a computable set. The second condition suggests why computably enumerable is used. The abbreviations c.e. and r.e. are often used, even in print, instead of the full phrase.

In computational complexity theory, the complexity class containing all computably enumerable sets is RE. In recursion theory, the lattice of c.e. sets under inclusion is denoted ${\displaystyle {\mathcal {E}}}$.

A set S of natural numbers is called computably enumerable if there is a partial computable function whose domain is exactly S, meaning that the function is defined if and only if its input is a member of S.

The following are all equivalent properties of a set S of natural numbers:

Semidecidability:

• The set S is computably enumerable. That is, S is the domain (co-range) of a partial computable function.
• The set S is ${\displaystyle \Sigma _{1}^{0}}$ (referring to the arithmetical hierarchy).^[1]
• 次のような部分計算可能関数fが存在する。$${\displaystyle f(x)={\begin{cases}1&{\mbox{if}}\ x\in S\\{\mbox{undefined/does not halt}}\ &{\mbox{if}}\ x\notin S\end{cases}}}$$

列挙可能性:

• 集合Sは、部分計算可能関数の値域である。
• 集合Sは、全計算可能関数の値域、または空集合です。S が無限集合の場合、関数は単射となるように選択できます。
• 集合Sは、原始再帰関数の値域、または空集合です。Sが無限集合であっても、この場合は値の繰り返しが必要になる場合があります。

ディオファントス：

• 整数係数と変数を持つ多項式pが存在する${\displaystyle x,a_{1},a_{2},a_{3},\dots ,a_{9}}$自然数の範囲で、$${\displaystyle x\in S\Leftrightarrow \exists a_{1},a_{2},a_{3},\dots ,a_{9}\ (p(x,a_{1},a_{2},a_{3},\dots ,a_{9})=0).}$$（この定義における束縛変数の数は、現時点で最もよく知られている数である。より少ない数で全てのディオファントス集合を定義できる可能性もある。）
• 整数から整数への多項式が存在し、集合Sはその値域内の非負の数をちょうど含む。

半決定可能性と列挙可能性の等価性は、ダブテイルイングの手法によって得られる。

計算可能列挙可能集合のディオファントス的特徴付けは、最初の定義ほど単純明快でも直感的でもないが、ヒルベルトの第10問題の否定的解の一部としてユーリ・マティヤセヴィチによって発見された。ディオファントス集合は再帰理論より前に存在しており、したがって歴史的にこれらの集合を記述する最初の方法である（ただし、この等価性は計算可能列挙可能集合の導入から30年以上経ってから指摘された）。^{[ 2 ]}

• 計算可能な集合はすべて計算可能列挙可能であるが、計算可能列挙可能な集合がすべて計算可能であるとは限らない。計算可能な集合の場合、アルゴリズムは入力が集合に含まれていないかどうかも判定する必要があるが、計算可能列挙可能な集合にはそのような要件はない。
• 再帰的に列挙可能な言語とは、形式言語の計算可能な列挙可能な部分集合のことである。
• 効果的に提示された公理系における証明可能なすべての文の集合は、計算可能な列挙可能な集合である。
• マティヤセヴィッチの定理は、計算可能なすべての集合はディオファントス集合であると述べている（逆は自明に真である）。
• 単純集合は計算上列挙可能であるが、計算可能ではない。
• 創造的集合は計算上列挙可能であるが、計算可能ではない。
• いかなる生産的集合も計算上列挙可能ではない。
• ゲーデル数化が与えられた場合${\displaystyle \phi }$計算可能な関数の集合${\displaystyle \{\langle i,x\rangle \mid \phi _{i}(x)\downarrow \}}$（どこ${\displaystyle \langle i,x\rangle }$はカントールペアリング関数であり、${\displaystyle \phi _{i}(x)\downarrow }$示す${\displaystyle \phi _{i}(x)}$（定義済み）は計算可能列挙可能（固定されたxの場合の図を参照）。この集合は、各チューリングマシンが停止する入力パラメータを記述することで、停止問題を符号化している。
• ゲーデル数化が与えられた場合${\displaystyle \phi }$計算可能な関数の集合${\displaystyle \{\left\langle x,y,z\right\rangle \mid \phi _{x}(y)=z\}}$計算可能列挙可能である。この集合は、関数値を決定する問題を符号化している。
• 自然数から自然数への部分関数fが与えられたとき、 fが部分計算可能関数であるのは、 fのグラフ、つまりすべてのペアの集合が${\displaystyle \langle x,f(x)\rangle }$f ( x )が定義されるようなは、計算可能列挙可能である。

AとBが計算可能集合である場合、 A ∩ B、A ∪ B、およびA × B（自然数の順序対がカントール対関数によって単一の自然数に写像される）は計算可能集合である。部分計算可能関数による計算可能集合の逆像は、計算可能集合である。

セット${\displaystyle T}$補集合が共計算可能列挙可能または co-ceである場合、補集合は共計算可能列挙可能またはco-ceと呼ばれます。${\displaystyle \mathbb {N} \setminus T}$は計算可能列挙可能である。言い換えれば、集合が共再集合であるのは、それがレベルにある場合に限る。${\displaystyle \Pi _{1}^{0}}$算術階層の。共計算可能列挙可能集合の複雑性クラスはco-REと表記される。

集合Aが計算可能であるのは、 AとAの補集合の両方が計算可能列挙可能である場合に限る。

計算可能な列挙可能な集合のペアの中には、実質的に分離可能なものとそうでないものが存在する。

自然数のすべての再帰的に列挙可能な部分集合の集合は、集合包含の下で半順序集合にすることができます。この半順序集合は束です。^{[ 3 ]}この束の理論は、決定不能問題であることが知られています。^{[ 3 ]}同様に、すべての計算可能列挙可能なベクトル空間の集合も束を形成します。^{[ 4 ]}実際、これをさらに一般化して、すべての再帰的に列挙可能なフィルタから構成される束 L(Q) にすることができます。ここで、Qは原子を持たない何らかの自由ブール代数です。^{[ 5 ]}これらの束は、再帰的に列挙可能なPi-0-1クラスの研究と密接に関連しています。^{[ 5 ]}

チャーチ＝チューリングのテーゼによれば、実質的に計算可能な関数はチューリングマシンで計算可能であり、したがって集合Sは、 Sの列挙を生成する何らかのアルゴリズムが存在する場合に限り、計算可能列挙可能である。しかし、チャーチ＝チューリングのテーゼは形式的な公理ではなく非形式的な予想であるため、これは形式的な定義とはみなせない。^{[ 8 ]}

現代の教科書では、計算可能列挙集合を、全計算可能関数の値域ではなく、部分関数の定義域として定義するのが一般的です。この選択の根拠は、 α-再帰理論のような一般化された再帰理論において、定義域に対応する定義の方がより自然であることが判明しているからです。他の教科書では、列挙という観点から定義を用いていますが、これは計算可能列挙集合の場合と同等です。

• RE（複雑性）
• 再帰的に列挙可能な言語
• 算術階層

• ロジャース、H. 『再帰関数と有効計算可能性の理論』MIT Press。ISBN 0-262-68052-1; ISBN 0-07-053522-1。
• Soare, R.再帰的に列挙可能な集合と次数。数理論理学の展望。Springer -Verlag、ベルリン、1987年。ISBN 3-540-15299-7。
• Soare, Robert I. 再帰的に列挙可能な集合と次数。Bull . Amer. Math. Soc. 84 (1978), no. 6, 1149–1181.