索引セット（計算可能性）

Classes of partial recursive functions

計算可能性理論において、指数集合は計算可能関数のクラスを記述します。具体的には、部分計算可能関数の 固定されたゲーデル数に従って、特定のクラスに属する関数のすべての指数を与えます

定義

をすべての部分計算可能関数の計算可能列挙とし、をすべての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{ is finite}}\}}$は-完了です。 ${\displaystyle \Sigma _{2}}$
• ${\displaystyle \mathrm {Inf} =\{e\,:\,W_{e}{\text{ is infinite}}\}}$は-完了です。 ${\displaystyle \Pi _{2}}$
• ${\displaystyle \mathrm {Tot} =\{e\,:\,\varphi _{e}{\text{ is total}}\}=\{e:W_{e}=\mathbb {N} \}}$は-完了です。 ${\displaystyle \Pi _{2}}$
• ${\displaystyle \mathrm {Con} =\{e\,:\,\varphi _{e}{\text{ is total and constant}}\}}$は-完了です。 ${\displaystyle \Pi _{2}}$
• ${\displaystyle \mathrm {Cof} =\{e\,:\,W_{e}{\text{ is cofinite}}\}}$は-完了です。 ${\displaystyle \Sigma _{3}}$
• ${\displaystyle \mathrm {Rec} =\{e\,:\,W_{e}{\text{ is computable}}\}}$は-完了です。 ${\displaystyle \Sigma _{3}}$
• ${\displaystyle \mathrm {Ext} =\{e\,:\,\varphi _{e}{\text{ is extendible to a total computable function}}\}}$は-完了です。 ${\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}}$

注釈

1. Odifreddi, PG Classical Recursion Theory, 第1巻; 151ページ
2. Soare, Robert I. (2016)、「チューリング還元可能性」、チューリング計算可能性、計算可能性の理論と応用、ベルリン、ハイデルベルク：Springer Berlin Heidelberg、pp.  51– 78、doi :10.1007/978-3-642-31933-4_3、ISBN 978-3-642-31932-72021年4月21日取得

参考文献

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

Retrieved from "https://en.wikipedia.org/w/index.php?title=Index_set_(computability)&oldid=1292130148"