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

en:Recursively enumerable set(版:02:38, 9 August 2008)に基づき修正
m編集の要約なし
(en:Recursively enumerable set(版:02:38, 9 August 2008)に基づき修正)
'''帰納的可算集合'''([[英語|英]]: '''Recursively enumerable set''')とは、[[計算理論]]または[[再帰理論]]におけるある種の[[集合]]に付与された名前。[[自然数]]の[[集合]] ''S'' について以下が成り立つ場合、その集合を指して'''帰納的可算'''、'''計算可枚挙'''、'''半決定可能'''、'''証明可能'''、'''チューリング-認識可能'''などと称
 
* ある[[アルゴリズム]]に入力となる数を与えたとき、そのアルゴリズムが停止する必要十分条件が、その数が ''S'' の元であるきのみアルゴリズムが停止すである。
 
あるいは、これと同値だが
 
* ''S'' の元の個数を[[数え上げ|枚挙]]るアルゴリズムが存在する。つまり、その出力は ''S'' の元のリスト ''s''<sub>1</sub>, ''s''<sub>2</sub>, ''s''<sub>3</sub>, ... である。このアルゴリズムは必要ならば無限に動作する。
 
前者の条件から、これ'''半決定可能集合'''(semidecidable set)(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'' はその値域の非負数だけを正確に含む。
 
最後のは最初の定義から単純に導かれるものではないが、[[ヒルベルトの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'' が部分再帰関数である必要十分条件は、''f(x)'' が定義されていような全ての対 <math>\langle x,f(x)\rangle</math> の集合が帰納的可算であるきだけ、''f'' は部分再帰関数である。
 
== 特性 ==
''A'' と ''B'' が共に帰納的可算集合なら、''A'' ∩ ''B'' ''A'' ∪ ''B'' ''A'' × ''B'' も帰納的可算集合である(''A'' × ''B'' は、[[対関数|カントールの対関数]]を使って順序対を1つの自然数にすることを意味する)。部分再帰関数における帰納的可算集合の逆像は帰納的可算集合である。
 
ある集合が帰納的可算である必要十分条件は、それが[[算術的階層]]のレベル <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'' の補集合が共に帰納的可算集合であることである。ある集のみ[[帰納的である必要十分条件は、その集合|が何らかの全体再納的]](計算可能)関数の昇順の値域になっているか、または有限なことである。
 
帰納的可算集合同士の対を取ると、あるものは有効に分離可能([[:en:effectively separable|en]])であり、あるものは有効に分離不可能である。
 
== 注意 ==
[[チャーチ=チューリングのテーゼ]]によれば、有効に計算可能な関数は全て[[チューリングマシン]]で計算可能であり、従って集合 ''S'' が帰納的可算である必要十分条件何らかの[[アルゴリズム]]で ''S'' の数え上げ枚挙ができる場合のみ帰納的可算ことである。しかしこれを形式的お、定義とすることはできない。何故ならチャーチ=チューリングのテーゼ形式的な公理ではないためこれも形式的定義にでき予想だからである
 
最近の文献では、帰納的可算集合を全体再帰関数の「値域」ではなく、部分関数の「定義域」として定義する方が最近では一般的である。この理由最近、例えば[[α-再帰理論]]([[:en:Alpha recursion theory|en]])ような一般化された再帰理論では、定義域を用いた定義ほうが自然であるだと判ったためである。他の分野文献では数え上げ枚挙を使った定義がよく使われるが、これも帰納的可算集合に同値である。
 
== 参考文献 ==