「帰納的可算集合」の版間の差分

削除された内容追加された内容

インライン

2008年11月26日 (水) 10:19時点における版

帰納的可算集合（英: 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}}$ と書く。

形式的定義

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

この定義は任意の可算集合 A に拡張できる。そのためには、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年以上も後のことである）。上記の式における束縛変数の個数はこれまでのところ最小とされているもので、もっと少ない個数でディオファントス集合を表せる可能性はある。

例

全ての帰納的集合は帰納的可算だが、全ての帰納的可算集合が帰納的（集合）とは言えない。
帰納的可算言語は形式言語の帰納的可算な部分集合である。
妥当な公理系から導かれる全ての文の集合は、帰納的可算集合である。
マチャセビッチの定理によれば、全ての帰納的可算集合はディオファントス集合である（逆も明らかに真）。
単純集合は帰納的可算だが帰納的でない。
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 が部分再帰関数である必要十分条件は、f(x) が定義されるような全ての対 $\langle x,f(x)\rangle$ の集合が帰納的可算であることである。

特性

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 の補集合が共に帰納的可算集合であることである。ある集合が帰納的である必要十分条件は、その集合が何らかの全体再帰関数の昇順の値域になっているか、または有限なことである。

帰納的可算集合同士の対を取ると、あるものは有効に分離可能(en)であり、あるものは有効に分離不可能である。

注意

チャーチ＝チューリングのテーゼによれば、有効に計算可能な関数は全てチューリングマシンで計算可能であり、従って集合 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.

@@ 1行目: / 1行目: @@
-'''帰納的可算集合'''（[[英語|英]]: '''Recursively enumerable set'''）とは、[[自然数]]の[[集合]] ''S'' について、以下が成り立つ場合を指す。
+'''帰納的可算集合'''（[[英語|英]]: '''Recursively enumerable set'''）とは、[[計算理論]]または[[再帰理論]]におけるある種の[[集合]]に付与された名前。[[自然数]]の[[集合]] ''S'' について以下が成り立つ場合、その集合を指して'''帰納的可算'''、'''計算可枚挙'''、'''半決定可能'''、'''証明可能'''、'''チューリング-認識可能'''などと称する。
-* ある[[アルゴリズム]]に入力となる数を与えたとき、その数が ''S'' の元であるときのみアルゴリズムが停止する。
+* ある[[アルゴリズム]]に入力となる数を与えたとき、そのアルゴリズムが停止する必要十分条件が、その数が ''S'' の元であることである。
-あるいは、
+あるいは、これと同値だが、
-* ''S'' の元の個数を[[数え上げ]]るアルゴリズムが存在する。つまり、その出力は ''S'' の元のリスト ''s''<sub>1</sub>, ''s''<sub>2</sub>, ''s''<sub>3</sub>, ... である。このアルゴリズムは必要ならば無限に動作する。
+* ''S'' の元を[[数え上げ|枚挙]]するアルゴリズムが存在する。つまり、その出力は ''S'' の元のリスト ''s''<sub>1</sub>, ''s''<sub>2</sub>, ''s''<sub>3</sub>, ... である。このアルゴリズムは必要ならば無限に動作する。
-前者の条件から、これを'''半決定可能集合'''（semidecidable set）と呼ぶことがある。また、後者の条件から'''計算可枚挙集合'''（computably enumerable set）とも呼ぶ。略記法として '''r.e.''' あるいは '''c.e.''' とされることも多い。
+これが'''半決定可能集合''' (semidecidable set) と時に呼ばれるのは前者の条件に由来する。また、'''計算可枚挙集合'''（computably enumerable set）という用語は後者の条件に由来する。略して '''r.e.''' あるいは '''c.e.''' と書くが、これは出版物にもよく出現する。
-[[計算複雑性理論]]において、全ての帰納的可算集合を包含する[[複雑性クラス]]を '''[[RE (計算複雑性理論)|RE]]''' と呼ぶ。
+[[計算複雑性理論]]において、全ての帰納的可算集合を包含する[[複雑性クラス]]を '''[[RE (計算複雑性理論)|RE]]''' と呼ぶ。[[再帰理論]]においては、 包含された r.e. 集合の[[束論|束]] (lattice) を <math>\mathcal{E}</math> と書く。
 == 形式的定義 ==
-自然数の集合 ''S'' が'''帰納的可算'''であると言われる場合、関数への入力が ''S'' の元であるときだけ値が定義されるような部分再帰（[[計算可能関数|計算可能]]）関数が存在する。すなわち定義域が正確に ''S'' に対応する関数である。
+[[自然数]]の集合 ''S'' について、定義域が ''S'' と正確に一致するような何らかの部分再帰関数（[[計算可能関数|部分計算可能関数]]）''f'' が存在するとき、''S'' は'''帰納的可算'''であると言う。つまり ''f'' が定義される必要十分条件は、''f'' への入力が ''S'' の元であることである。
-この定義は[[ゲーデル数]]を使って任意の集合 ''A'' の元を表現することで拡張可能であり、''A'' の部分集合が帰納的可算であるとは、対応するゲーデル数の集合が帰納的可算であることを意味する。
+この定義は任意の可算集合 A に拡張できる。そのためには、A の元を[[ゲーデル数]]で表し、もし対応するゲーデル数の集合が帰納的加算ならば A の何らかの部分集合が帰納的可算になることを言えば良い。
 == 等価な定式化 ==
@@ 37行目: / 37行目: @@
 :* 整数群から整数群への多項式があり、集合 ''S'' はその値域の非負数だけを正確に含む。
-最後のは最初の定義から単純に導かれるものではないが、[[ヒルベルトの23の問題|ヒルベルトの第10問題]]を解く過程で[[ユーリ・マチャセビッチ]]が発見した。ディオファントス集合は[[再帰理論]]に先行しているため、歴史的にはこれが帰納的可算集合の最初の定義であった（ただし、これらが同じものを表していると分かったのは帰納的可算集合が登場してから30年ほど後のことである）。上記の式における[[束縛変数]]の個数はこれまでのところ最小とされているもので、もっと少ない個数でディオファントス集合を表せる可能性はある。
+最後のは最初の定義から単純に導かれるものではないが、[[ヒルベルトの23の問題|ヒルベルトの第10問題]]を否定的に解決する過程で[[ユーリ・マチャセビッチ]]が発見した。ディオファントス集合は[[再帰理論]]に先行しているため、歴史的にはこれが帰納的可算集合の最初の定義であった（ただし、これらが同じものを表していると分かったのは帰納的可算集合が登場してから30年以上も後のことである）。上記の式における[[束縛変数]]の個数はこれまでのところ最小とされているもので、もっと少ない個数でディオファントス集合を表せる可能性はある。
 == 例 ==
-* 全ての[[帰納的集合]]は帰納的可算であるが、全ての帰納的可算集合が帰納的（集合）とは言えない。
+* 全ての[[帰納的集合]]は帰納的可算だが、全ての帰納的可算集合が帰納的（集合）とは言えない。
-* [[帰納的可算言語]]は帰納的可算な[[形式言語]]の部分集合である。
+* [[帰納的可算言語]]は[[形式言語]]の帰納的可算な部分集合である。
 * 妥当な公理系から導かれる全ての文の集合は、帰納的可算集合である。
 * マチャセビッチの定理によれば、全ての帰納的可算集合はディオファントス集合である（逆も明らかに真）。
-* simple set と creative set は帰納的可算だが帰納的でない。
+* [[単純集合]]は帰納的可算だが帰納的でない。
+* creative set は帰納的可算だが帰納的でない。
 * productive set は帰納的可算ではない。
 * ある計算可能関数にゲーデル数 <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(x)'' が定義されている全ての対 <math>\langle x,f(x)\rangle</math> の集合が帰納的可算であるときだけ、''f'' は部分再帰関数である。
+* 自然数から自然数への部分関数 ''f'' があるとき、''f'' が部分再帰関数である必要十分条件は、''f(x)'' が定義されるような全ての対 <math>\langle x,f(x)\rangle</math> の集合が帰納的可算であることである。
 == 特性 ==
-''A'' と ''B'' が共に帰納的可算集合なら、''A'' ∩ ''B'' も ''A'' ∪ ''B'' も ''A'' × ''B'' も帰納的可算集合である（''A'' × ''B'' は、対関数を使って順序対を1つの自然数にすることを意味する）。部分再帰関数における帰納的可算集合の逆像は帰納的可算集合である。
+''A'' と ''B'' が共に帰納的可算集合なら、''A'' ∩ ''B'' 、 ''A'' ∪ ''B'' 、 ''A'' × ''B'' も帰納的可算集合である（''A'' × ''B'' は、[[対関数|カントールの対関数]]を使って順序対を1つの自然数にすることを意味する）。部分再帰関数における帰納的可算集合の逆像は帰納的可算集合である。
-ある集合が帰納的可算であるのは、それが[[算術的階層]]のレベル <math>\Sigma^0_1</math> にある場合のみである。
+ある集合が帰納的可算である必要十分条件は、それが[[算術的階層]]のレベル <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> にある場合のみである。
+集合 <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'' の補集合も帰納的可算集合である場合のみ[[帰納的集合|帰納的]]（計算可能）である。
+集合 ''A'' が[[帰納的集合|帰納的]]（計算可能）である必要十分条件は、''A'' と ''A'' の補集合が共に帰納的可算集合であることである。ある集合が帰納的である必要十分条件は、その集合が何らかの全体再帰関数の昇順の値域になっているか、または有限なことである。
+帰納的可算集合同士の対を取ると、あるものは有効に分離可能([[:en:effectively separable|en]])であり、あるものは有効に分離不可能である。
 == 注意 ==
-[[チャーチ＝チューリングのテーゼ]]によれば、有効に計算可能な関数は全て[[チューリングマシン]]で計算可能であり、従って集合 ''S'' は何らかの[[アルゴリズム]]で ''S'' の数え上げができる場合のみ帰納的可算である。なお、チャーチ＝チューリングのテーゼが形式的な公理ではないため、これも形式的定義にできない。
+[[チャーチ＝チューリングのテーゼ]]によれば、有効に計算可能な関数は全て[[チューリングマシン]]で計算可能であり、従って集合 ''S'' が帰納的可算である必要十分条件は、何らかの[[アルゴリズム]]で ''S'' の枚挙ができることである。しかしこれを形式的な定義とすることはできない。何故ならチャーチ＝チューリングのテーゼは形式的な公理ではなく、非形式的な予想だからである。
-帰納的可算集合を全体再帰関数の「値域」ではなく、部分関数の「定義域」として定義する方が最近では一般的である。これは最近の再帰理論でそのほうが自然であるためである。他の分野では数え上げを使った定義がよく使われる。
+最近の文献では、帰納的可算集合を全体再帰関数の「値域」ではなく、部分関数の「定義域」として定義する方が一般的である。この理由は、例えば[[α-再帰理論]]([[:en:Alpha recursion theory|en]])のような一般化された再帰理論では、定義域を用いた定義の方が自然だと判ったためである。他の文献では枚挙を使った定義がよく使われるが、これも帰納的可算集合に同値である。
 == 参考文献 ==