インデックスセット（計算可能性）

計算可能性理論では、インデックス セットは計算可能な関数のクラスを記述します。具体的には、部分計算可能な関数の固定されたゲーデル番号に従って、特定のクラス内の関数のすべてのインデックスを提供します。

をすべての部分計算可能関数の計算可能列挙とし、をすべてのce 集合の計算可能列挙とします。 ${\displaystyle \varphi_{e}}$${\displaystyle W_{e}}$

を部分計算可能関数のクラスとします。のとき、は のインデックス セットです。一般に、を持つ任意の に対して(つまり、同じ関数をインデックスする)、 が成り立つとき、 はインデックス セットです。直感的には、これらは、インデックスする関数を参照してのみ記述される自然数の集合です。 ${\displaystyle {\mathcal {A}}}$${\displaystyle A=\{x\,:\,\varphi _{x}\in {\mathcal {A}}\}}$${\displaystyle A}$${\displaystyle {\mathcal {A}}}$${\displaystyle A}$${\displaystyle x,y\in \mathbb {N} }$${\displaystyle \varphi _{x}\simeq \varphi _{y}}$${\displaystyle x\in A\leftrightarrow y\in A}$

2 つの些細な例外を除いて、ほとんどのインデックス セットは計算不可能です。これはライスの定理で述べられています。

を、インデックスが である部分計算可能関数のクラスとします。が計算可能であるのは、が空であるか、 がすべて である場合のみです。${\displaystyle {\mathcal {C}}}$${\displaystyle C}$${\displaystyle C}$${\displaystyle C}$${\displaystyle C}$${\displaystyle \mathbb {N} }$

ライスの定理によれば、「部分計算可能関数の任意の非自明な性質は決定不可能である」とされている。^[1]

指数集合は、算術階層のあるレベルで完全な集合の例を数多く提供します。ここで、任意の集合に対してからへのm-還元が存在する場合、集合は-完全であると言います。-完全性も同様に定義されます。以下にいくつか例を示します。^[2]${\displaystyle \Sigma _{n}}$${\displaystyle A}$${\displaystyle \Sigma _{n}}$${\displaystyle \Sigma _{n}}$${\displaystyle B}$${\displaystyle B}$${\displaystyle A}$${\displaystyle \Pi_{n}}$

• ${\displaystyle \mathrm {Emp} =\{e\,:\,W_{e}=\varnothing \}}$完了です。${\displaystyle \Pi_{1}}$
• ${\displaystyle \mathrm {Fin} =\{e\,:\,W_{e}{\text{ は有限です}}\}}$完了です。${\displaystyle \Sigma _{2}}$
• ${\displaystyle \mathrm {Inf} =\{e\,:\,W_{e}{\text{ は無限大}}\}}$完了です。${\displaystyle \Pi_{2}}$
• ${\displaystyle \mathrm {Tot} =\{e\,:\,\varphi _{e}{\text{ は合計}}\}=\{e:W_{e}=\mathbb {N} \} }$完了です。${\displaystyle \Pi_{2}}$
• ${\displaystyle \mathrm {Con} =\{e\,:\,\varphi _{e}{\text{ は合計で定数です}}\}}$完了です。${\displaystyle \Pi_{2}}$
• ${\displaystyle \mathrm {Cof} =\{e\,:\,W_{e}{\text{ は余剰である}}\}}$完了です。${\displaystyle \Sigma _{3}}$
• ${\displaystyle \mathrm {Rec} =\{e\,:\,W_{e}{\text{ は計算可能}}\}}$完了です。${\displaystyle \Sigma _{3}}$
• ${\displaystyle \mathrm {Ext} =\{e\,:\,\varphi _{e}{\text{ は全計算可能関数に拡張可能}}\}}$完了です。${\displaystyle \Sigma _{3}}$
• ${\displaystyle \mathrm {Cpl} =\{e\,:\,W_{e}\equiv _{\mathrm {T} }\mathrm {HP} \}}$は -完全ですが、停止問題はです。${\displaystyle \Sigma _{4}}$${\displaystyle \mathrm {HP} }$

経験的に、集合の「最も明白な」定義が[resp. ]である場合、通常、 が-完全 [resp. -完全]であることを示すことができます。 ${\displaystyle A}$${\displaystyle \Sigma _{n}}$${\displaystyle \Pi_{n}}$${\displaystyle A}$${\displaystyle \Sigma _{n}}$${\displaystyle \Pi_{n}}$

• オディフレディ、 PG (1992)。古典的再帰理論、第1巻。エルゼビア。p.668。ISBN 0-444-89483-7。
• ロジャース・ジュニア、ハートリー（1987年）。再帰関数と実効計算可能性の理論。MITプレス。p.482。ISBN 0-262-68052-1。