帰納的可算集合

帰納的可算集合（英: Recursively enumerable set）とは、自然数の集合 S について、以下が成り立つ場合を指す。

• あるアルゴリズムに入力となる数を与えたとき、その数が S の元であるときのみアルゴリズムが停止する。

あるいは、

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

前者の条件から、これを半決定可能集合（semidecidable set）と呼ぶことがある。また、後者の条件から計算可枚挙集合（computably enumerable set）とも呼ぶ。略記法として r.e. あるいは c.e. とされることも多い。

計算複雑性理論において、全ての帰納的可算集合を包含する複雑性クラスを RE (計算複雑性理論) と呼ぶ。

形式的定義

自然数の集合 S が帰納的可算であると言われる場合、関数への入力が S の元であるときだけ値が定義されるような部分再帰（計算可能）関数が存在する。すなわち定義域が正確に S に対応する関数である。

この定義はゲーデル数を使って任意の集合 A の元を表現することで拡張可能であり、A の部分集合が帰納的可算であるとは、対応するゲーデル数の集合が帰納的可算であることを意味する。

等価な定式化

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

半決定可能性:

• 集合 S は帰納的可算である。すなわち、S はある部分再帰関数の定義域である。
• 次のような部分再帰関数 f が存在する:

$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).$

• 整数群から整数群への多項式があり、集合 S はその値域の非負数だけを正確に含む。

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

例

• 全ての帰納的集合は帰納的可算であるが、全ての帰納的可算集合が帰納的（集合）とは言えない。
• 帰納的可算言語は帰納的可算な形式言語の部分集合である。
• 妥当な公理系から導かれる全ての文の集合は、帰納的可算集合である。
• マチャセビッチの定理によれば、全ての帰納的可算集合はディオファントス集合である（逆も明らかに真）。
• simple set と creative set は帰納的可算だが帰納的でない。
• productive set は帰納的可算ではない。
• ある計算可能関数にゲーデル数 $\phi$ が与えられたとき、集合 $\{\langle i,x\rangle \mid \phi _{i}(x)\downarrow \}$ は帰納的可算である（ここで、$\langle i,x\rangle$ は対関数であり、$\phi _{i}(x)\downarrow$ は $\phi _{i}(x)$ が定義されていることを示す）。この集合は、チューリングマシンが停止する入力パラメータ群を表すことで、チューリングマシンの停止問題の符号化となる。
• ある計算可能関数にゲーデル数 $\phi$ が与えられたとき、集合 $\lbrace \left\langle x,y,z\right\rangle \mid \phi _{x}(y)=z\rbrace$ は帰納的可算である。この集合は関数値を決定する問題の符号化である。
• 自然数から自然数への部分関数 f があるとき、f(x) が定義されている全ての対 $\langle x,f(x)\rangle$ の集合が帰納的可算であるときだけ、f は部分再帰関数である。

特性

A と B が共に帰納的可算集合なら、A ∩ B も A ∪ B も A × B も帰納的可算集合である（A × B は、対関数を使って順序対を1つの自然数にすることを意味する）。部分再帰関数における帰納的可算集合の逆像は帰納的可算集合である。

ある集合が帰納的可算であるのは、それが算術的階層のレベル $\Sigma _{1}^{0}$ にある場合のみである。

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

集合 A は、A も A の補集合も帰納的可算集合である場合のみ帰納的（計算可能）である。

注意

チャーチ＝チューリングのテーゼによれば、効率的に計算可能な関数は全てチューリングマシンで計算可能であり、従って集合 S は何らかのアルゴリズムで S の数え上げができる場合のみ帰納的可算である。なお、チャーチ＝チューリングのテーゼが形式的な公理ではないため、これも形式的定義にできない。

帰納的可算集合を全体再帰関数の「値域」ではなく、部分関数の「定義域」として定義する方が最近では一般的である。これは最近の再帰理論でそのほうが自然であるためである。他の分野では数え上げを使った定義がよく使われる。

参考文献

• 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.