帰納的可算集合のソースを表示

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

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

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

* ''S'' の元を[[数え上げ|枚挙]]するアルゴリズムが存在する。つまり、その出力は ''S'' の元のリスト ''s''<sub>1</sub>, ''s''<sub>2</sub>, ''s''<sub>3</sub>, ... である。このアルゴリズムは必要ならば無限に動作する。

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

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

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

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

== 等価な定式化 ==
以下は、自然数の集合 ''S'' について同じ特性を表現したものである。

; 半決定可能性
:* 集合 ''S'' は帰納的可算である。すなわち、''S'' はある部分再帰関数の定義域である。
:* 次のような部分再帰関数 ''f'' が存在する:
::<math>f(x) = 
\left\{\begin{matrix} 
0 &\mbox{if}\ x \in S \\
\mbox{undefined/does not halt}\ &\mbox{if}\ x \notin S
\end{matrix}\right.
</math>
; 可算性
:* 集合 ''S'' は、部分再帰関数の値域である。
:* 集合 ''S'' は、全体再帰関数の値域であるか空である。''S'' が無限の場合、その関数は[[単射]]でもよい。
:* 集合 ''S'' は、[[原始再帰関数]]の値域であるか空である。''S'' が無限であっても、単射とはならない。
; [[ディオファントス方程式]]
:* 次のような整数係数の多項式 ''p'' があり、変数 ''x'', ''a'', ''b'', ''c'', ''d'', ''e'', ''f'', ''g'', ''h'', ''i'' の値域が自然数全体に及んでいる。
::<math>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).</math>
:* 整数群から整数群への多項式があり、集合 ''S'' はその値域の非負数だけを正確に含む。

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

== 例 ==
* 全ての[[帰納的集合]]は帰納的可算だが、全ての帰納的可算集合が帰納的（集合）とは言えない。
* [[帰納的可算言語]]は[[形式言語]]の帰納的可算な部分集合である。
* 帰納的可算な公理系から導かれる全ての文の集合は帰納的可算集合である。
* マチャセビッチの定理によれば、全ての帰納的可算集合はディオファントス集合である（逆も明らかに真）。
* [[単純集合]]は帰納的可算だが帰納的でない。
* [[創造的集合]]は帰納的可算だが帰納的でない。
* [[生産的集合]]は帰納的可算ではない。
* ある計算可能関数にゲーデル数 <math>\phi</math> が与えられたとき、集合 <math>\{\langle i,x \rangle \mid \phi_i(x) \downarrow \}</math> は帰納的可算である（ここで、<math>\langle i,x \rangle</math> は[[対関数]]であり、<math>\phi_i(x)\downarrow</math> は <math>\phi_i(x)</math> が定義されていることを示す）。この集合は、[[チューリングマシン]]が停止する入力パラメータ群を表すことで、[[チューリングマシンの停止問題]]の符号化となる。
* ある計算可能関数にゲーデル数 <math>\phi</math> が与えられたとき、集合 <math>\lbrace \left \langle x, y, z \right \rangle \mid \phi_x(y)=z \rbrace</math> は帰納的可算である。この集合は関数値を決定する問題の符号化である。
* 自然数から自然数への部分関数 ''f'' があるとき、''f'' が部分再帰関数である必要十分条件は、''f(x)'' が定義されるような全ての対 <math>\langle x,f(x)\rangle</math> の集合が帰納的可算であることである。

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

ある集合が帰納的可算である必要十分条件は、それが[[算術的階層]]のレベル <math>\Sigma^0_1</math> にあることである。

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

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

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

任意の帰納的可算集合 <math>A,B</math> に対して、互いに素な帰納的可算集合 <math>\tilde{A},\tilde{B}</math> で <math>\tilde{A} \subseteq A</math>, <math>\tilde{B} \subseteq B</math>, <math>\tilde{A} \cup \tilde{B} = A \cup B</math> なるものが存在する。<math>A,B</math> の元を <math>a_0, b_0, a_1, b_1, \ldots </math> と交互に枚挙していく。<math>a_i</math> がそれより前に現れないなら <math>\tilde{A}</math> に置く。また <math>b_i</math> がそれより前に現れないなら <math>\tilde{B}</math> に置く。このとき <math>\tilde{A},\tilde{B}</math> は所望の性質を満たす。

任意の帰納的でない帰納的可算集合は2つの互いに素な帰納的でない帰納的可算集合に直和分解できる。<ref>Richard M. Friedberg (1958), ''Three Theorems on Recursive Enumeration. I. Decomposition. II. Maximal Set. III. Enumeration Without Duplication'', ''Journal of Symbolic Logic'' 23:3, pp.&nbsp;309–316.</ref>

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

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

== 脚注 ==
{{reflist}}

== 参考文献 ==
* 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.

{{DEFAULTSORT:きのうてきかさんしゆうこう}}

[[Category:数理論理学]]
[[Category:計算理論]]
[[Category:数学に関する記事]]