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

計算可能性理論では、自然数の集合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は（算術階層を参照）である。^[1]${\displaystyle \Sigma _{1}^{0}}$
• 次のような部分計算可能関数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が無限であっても、この場合は値の繰り返しが必要になることがあります。

ディオファントス:

• 整数係数と自然数にわたる変数x、a、b、c、d、e、f、g、h、iを持つ多項式pが存在し、 (この定義における束縛変数の数は、これまで知られている中で最も多い数です。より少ない数を使用してすべてのディオファントス集合を定義できる可能性があります。)$${\displaystyle x\in S\Leftrightarrow \exists a,b,c,d,e,f,g,h,i\ (p(x,a,b,c,d,e,f,g,h,i)=0).}$$
• 整数から整数への多項式が存在し、集合Sにはその範囲内の非負の数が正確に含まれる。

半決定可能性と列挙可能性の同値性は、 dovetailingの手法によって得られます。

計算可能可算集合のディオファントス的特徴付けは、最初の定義ほど単純でも直感的でもないが、ユーリ・マティヤセビッチによってヒルベルトの第 10 問題の否定的解決の一部として発見された。ディオファントス集合は再帰理論より古く、したがって歴史的にはこれらの集合を記述する最初の方法である (ただし、この同等性は計算可能可算集合の導入から 30 年以上経って初めて指摘された)。

• すべての計算可能集合は計算可能列挙可能ですが、すべての計算可能列挙可能集合が計算可能であるとは限りません。計算可能集合の場合、アルゴリズムは入力が集合内に存在しないかどうかも判断する必要がありますが、これは計算可能列挙可能集合では必須ではありません。
• 再帰的に列挙可能な言語は、形式言語の計算可能に列挙可能なサブセットです。
• 効果的に提示された公理系におけるすべての証明可能な文の集合は、計算可能に列挙可能な集合です。
• マティヤセビッチの定理は、計算可能に可算なすべての集合はディオファントス集合である（逆は自明に真である）ことを述べています。
• 単純集合は計算可能に列挙可能ですが、計算可能ではありません。
• クリエイティブセットは計算可能に列挙可能ですが、計算可能ではありません。
• いかなる生成集合も計算可能に列挙可能ではありません。
• 計算可能関数のゲーデル番号付け が与えられると、集合( はカントールのペアリング関数であり、 が定義されていることを示す) は計算可能に列挙可能になります (固定されたxの図を参照)。この集合は、各チューリング マシンが停止する入力パラメータを記述するため、停止問題をエンコードします。${\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)}$
• 計算可能な関数のゲーデル番号が与えられれば、その集合は計算可能に列挙可能です。この集合は関数値を決定する問題をエンコードします。${\displaystyle \phi}$${\displaystyle \{\left\langle x,y,z\right\rangle \mid \phi _{x}(y)=z\}}$
• 自然数から自然数への部分関数fが与えられたとき、 fのグラフ、つまり f ( x ) が定義されるすべてのペアの集合が計算可能に列挙可能である場合のみ、fは部分計算可能関数である。${\displaystyle \langle x,f(x)\rangle }$

AとB が計算可能列挙集合である場合、 A ∩ B、A ∪ B、およびA × B (カントールペアリング関数を使用して単一の自然数にマッピングされた自然数の順序付きペア) は計算可能列挙集合です。部分計算可能関数による計算可能列挙集合の 逆像は計算可能列挙集合です。

集合の補集合が計算可能列挙可能である場合、その集合は共計算可能列挙可能またはco-ceと呼ばれます。同様に、集合が算術階層のレベルにある場合のみ、集合は co-re です。共計算可能列挙可能な集合の計算量クラスは co-RE と表されます。 ${\displaystyle T}$ ${\displaystyle \mathbb {N} \setminus T}$${\displaystyle \Pi _{1}^{0}}$

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

計算可能に列挙可能な集合のペアの中には、事実上分離可能なものと分離不可能なものとがあります。

チャーチ＝チューリングのテーゼによれば、任意の効果的に計算可能な関数はチューリングマシンによって計算可能であり、したがって集合Sが計算可能に列挙可能であるのは、 Sの列挙を生成する何らかのアルゴリズムが存在する場合のみである。しかし、チャーチ＝チューリングのテーゼは正式な公理ではなく非公式の推測であるため、これを正式な定義としてとらえることはできない。

現代のテキストでは、計算可能列挙集合を、計算可能関数全体の範囲ではなく、部分関数の領域として定義することが一般的です。この選択は、 α再帰理論などの一般化された再帰理論では、領域に対応する定義がより自然であることが判明したという事実に基づいています。他のテキストでは、計算可能列挙集合と同等の列挙の観点から定義を使用しています。

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

• Rogers, 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。