帰納的可算集合

帰納的可算集合︵きのうてきかさんしゅうごう、英: Recursively enumerable set︶は、計算理論または再帰理論におけるある種の集合に付与された名前。自然数の集合 Sについて以下が成り立つ場合、その集合を指して帰納的可算、計算可枚挙、半決定可能、証明可能、チューリング-認識可能などと称する。

●あるアルゴリズムに入力となる数を与えたとき、そのアルゴリズムが停止する必要十分条件が、その数が Sの元であることである。

あるいは、これと同値だが、

●S の元を枚挙するアルゴリズムが存在する。つまり、その出力は Sの元のリスト s₁, s₂, s₃, ... である。このアルゴリズムは必要ならば無限に動作する。

これが半決定可能集合 (semidecidable set) と時に呼ばれるのは前者の条件に由来する。また、計算可枚挙集合︵computably enumerable set︶という用語は後者の条件に由来する。略して r.e. あるいは c.e. と書くが、これは出版物にもよく出現する。

計算複雑性理論において、全ての帰納的可算集合を包含する複雑性クラスを REと呼ぶ。再帰理論においては、 包含関係に基づく r.e. 集合の束 (lattice) を ${\mathcal {E}}$${\mathcal {E}}$と書く。

形式的定義

自然数の集合 Sについて、定義域が Sと正確に一致するような何らかの部分再帰関数︵部分計算可能関数︶f が存在するとき、S は帰納的可算であると言う。つまり fが定義される必要十分条件は、f への入力が Sの元であることである。

この定義は任意の可算集合Aに拡張できる。そのためには、Aの元をゲーデル数で表し、もし対応するゲーデル数の集合が帰納的可算ならばAの何らかの部分集合が帰納的可算になることを言えば良い。

等価な定式化

以下は、自然数の集合 Sについて同じ特性を表現したものである。

半決定可能性


●集合 Sは帰納的可算である。すなわち、S はある部分再帰関数の定義域である。

●次のような部分再帰関数 fが存在する:

${\displaystyle f($x)=\left\{{\begin{matrix}0&{\mbox{if}}\ x\in S\\{\mbox{undefined/does not halt}}\ &{\mbox{if}}\ x\notin S\end{matrix}}\right.} $f(x)=\left\{{\begin{matrix}0&{\mbox{if}}\ x\in S\\{\mbox{undefined/does not halt}}\ &{\mbox{if}}\ x\notin S\end{matrix}}\right.$
可算性


●集合 Sは、部分再帰関数の値域である。

●集合 Sは、全体再帰関数の値域であるか空である。S が無限の場合、その関数は単射でもよい。

●集合 Sは、原始再帰関数の値域であるか空である。S が無限であっても、単射とはならない。

ディオファントス方程式


●次のような整数係数の多項式 pがあり、変数 x, a, b, c, d, e, f, g, h, iの値域が自然数全体に及んでいる。

$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).$$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はその値域の非負数だけを正確に含む。

最後の性質は、最初の定義から単純に導かれるものではないが、ヒルベルトの第10問題を否定的に解決する過程でユーリ・マチャセビッチが発見した。ディオファントス集合は再帰理論に先行しているため、歴史的にはこれが帰納的可算集合の最初の定義であった︵ただし、これらが同じものを表していると分かったのは帰納的可算集合が登場してから30年以上も後のことである︶。上記の式における束縛変数の個数は、これまでのところ最小とされているもので、もっと少ない個数でディオファントス集合を表せる可能性はある。

例

●全ての帰納的集合は帰納的可算だが、全ての帰納的可算集合が帰納的︵集合︶とは言えない。

●帰納的可算言語は形式言語の帰納的可算な部分集合である。

●帰納的可算な公理系から導かれる全ての文の集合は帰納的可算集合である。

●マチャセビッチの定理によれば、全ての帰納的可算集合はディオファントス集合である︵逆も明らかに真︶。

●単純集合は帰納的可算だが帰納的でない。

●創造的集合は帰納的可算だが帰納的でない。

●生産的集合は帰納的可算ではない。

●ある計算可能関数にゲーデル数 $\phi$$\phi$が与えられたとき、集合 ${\displaystyle \{\langle i,x\rangle \mid \phi _{i}($x)\downarrow \}} $\{\langle i,x\rangle \mid \phi _{i}(x)\downarrow \}$は帰納的可算である︵ここで、$\langle i,x\rangle$$\langle i,x\rangle$ は対関数であり、${\displaystyle \phi _{i}($x)\downarrow } $\phi _{i}(x)\downarrow$ は ${\displaystyle \phi _{i}($x)} $\phi _{i}(x)$が定義されていることを示す︶。この集合は、チューリングマシンが停止する入力パラメータ群を表すことで、チューリングマシンの停止問題の符号化となる。

●ある計算可能関数にゲーデル数 $\phi$$\phi$が与えられたとき、集合 ${\displaystyle \lbrace \left\langle x,y,z\right\rangle \mid \phi _{x}($y)=z\rbrace } $\lbrace \left\langle x,y,z\right\rangle \mid \phi _{x}(y)=z\rbrace$は帰納的可算である。この集合は関数値を決定する問題の符号化である。

●自然数から自然数への部分関数 fがあるとき、f が部分再帰関数である必要十分条件は、f(x) が定義されるような全ての対 ${\displaystyle \langle x,f($x)\rangle } $\langle x,f(x)\rangle$の集合が帰納的可算であることである。

特性

A と Bが共に帰納的可算集合なら、A ∩ B、 A∪ B、 A× Bも帰納的可算集合である。部分再帰関数における帰納的可算集合の逆像は帰納的可算集合である。

ある集合が帰納的可算である必要十分条件は、それが算術的階層のレベル $\Sigma _{1}^{0}$$\Sigma _{1}^{0}$にあることである。

集合 $T$$T$の補集合 $\mathbb {N} \setminus T$$\mathbb {N} \setminus T$が帰納的可算である場合、$T$$T$ は co-r.e. と呼ばれる。同様に、ある集合が co-r.e. である必要十分条件は、それが算術的階層のレベル $\Pi _{1}^{0}$$\Pi _{1}^{0}$にあることである。

集合 Aが帰納的︵計算可能︶である必要十分条件は、A と Aの補集合が共に帰納的可算集合であることである。これは帰納的可算集合の束に於いて帰納的関数のクラスが定義可能であることを示す。︵すなわち補元を持つ元が帰納的可算集合である。︶ある集合が帰納的である必要十分条件は、その集合が何らかの単調増加な全域再帰関数の値域になっているか、または有限なことである。

互いに素な帰納的可算集合同士の対を取ると、あるものは帰納的分離可能であり、あるものは帰納的分離不可能である。対照的に、任意の互いに素な co-r.e. 集合対が帰納的分離可能であることが、次の性質から示される。

任意の帰納的可算集合 $A,B$$A,B$に対して、互いに素な帰納的可算集合 ${\tilde {A}},{\tilde {B}}$${\tilde {A}},{\tilde {B}}$で ${\tilde {A}}\subseteq A$${\tilde {A}}\subseteq A$, ${\tilde {B}}\subseteq B$${\tilde {B}}\subseteq B$, ${\tilde {A}}\cup {\tilde {B}}=A\cup B$${\tilde {A}}\cup {\tilde {B}}=A\cup B$なるものが存在する。$A,B$$A,B$ の元を $a_{0},b_{0},a_{1},b_{1},\ldots$$a_{0},b_{0},a_{1},b_{1},\ldots$と交互に枚挙していく。$a_{i}$$a_{i}$ がそれより前に現れないなら ${\tilde {A}}$${\tilde {A}}$に置く。また $b_{i}$$b_{i}$がそれより前に現れないなら ${\tilde {B}}$${\tilde {B}}$に置く。このとき ${\tilde {A}},{\tilde {B}}$${\tilde {A}},{\tilde {B}}$は所望の性質を満たす。

任意の帰納的でない帰納的可算集合は2つの互いに素な帰納的でない帰納的可算集合に直和分解できる。

注意

チャーチ＝チューリングのテーゼによれば、実効的に計算可能な関数は全てチューリングマシンで計算可能であり、従って集合 Sが帰納的可算である必要十分条件は、何らかのアルゴリズムで Sの枚挙ができることである。しかしこれを形式的な定義とすることはできない。何故ならチャーチ＝チューリングのテーゼは形式的な公理ではなく、非形式的な予想だからである。

最近の文献では、帰納的可算集合を全体再帰関数の﹁値域﹂ではなく、部分関数の﹁定義域﹂として定義する方が一般的である。この理由は、例えばα-再帰理論(en)のような一般化された再帰理論では、定義域を用いた定義の方が自然だと判ったためである。他の文献では枚挙を使った定義がよく使われるが、これも帰納的可算集合に同値である。

参考文献

• Rogers, H. The Theory of Recursive Functions and Effective Computability, MIT Press. ISBN 0-262-68052-1; ISBN 0-07-053522-1.
• Soare, R. Recursively enumerable sets and degrees. Perspectives in Mathematical Logic. Springer-Verlag, Berlin, 1987. ISBN 3-540-15299-7.
• Soare, Robert I. Recursively enumerable sets and degrees. Bull. Amer. Math. Soc. 84 (1978), no. 6, 1149–1181.