計算可能な列挙可能な集合

計算可能性理論において、自然数の集合Sは、以下の条件を満たす場合に、計算可能列挙可能（ce）、再帰的列挙可能（re）、半決定可能、部分決定可能、列挙可能、証明可能、またはチューリング認識可能と呼ばれる。

• アルゴリズムが停止する入力数値の集合がちょうどSとなるようなアルゴリズムが存在する。

あるいは同等に、

• Sの要素を列挙するアルゴリズムがあります。つまり、その出力はSのすべての要素のリスト s ₁ , s ₂ , s ₃ , ... となります。S が無限の場合、このアルゴリズムは永久に実行されますが、S の各要素は有限時間後に返されます。これらの要素は、小さい順から大きい順など、特定の順序でリストされる必要はありません。

最初の条件は、半決定可能という用語が時々使用される理由を示しています。より正確には、ある数が集合に含まれている場合は、アルゴリズムを実行することでこれを決定できますが、その数が集合に含まれていない場合は、アルゴリズムは永遠に実行され、情報は返されません。「完全に決定可能」な集合は、計算可能集合です。2番目の条件は、計算可能列挙可能という用語が使用される理由を示しています。完全な語句の代わりに、印刷物でも、ceとreという略語がよく使用されます。

計算複雑性理論では、すべての計算可能列挙可能集合を含む複雑性クラスはREです。再帰理論では、包含関係にある ce 集合の束は次のように表されます。${\displaystyle {\mathcal {E}}}$。

自然数の集合Sは、定義域がSと完全に一致する部分計算可能関数が存在する場合、計算可能列挙可能であると呼ばれる。つまり、その関数は、入力がSの要素である場合に限り定義される。

自然数の集合Sの同値な性質は以下のとおりです。

半決定可能性：

• 集合Sは計算可能列挙可能である。すなわち、Sは部分計算可能関数の定義域（余値域）である。
• 集合Sは${\displaystyle \Sigma _{1}^{0}}$（算術階層を参照）。^{[ 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.