帰納的可算言語のソースを表示

'''帰納的可算言語'''（きのうてきかさんげんご、{{lang-en-short|Recursively enumerable language}}）は、[[数学]]・[[論理学]]・[[計算機科学]]における[[形式言語]]の一種である。'''部分決定性言語'''（Partially Decidable Language）、'''チューリング受理性言語'''（Turing-recognizable Language）とも呼ぶ。形式言語の[[チョムスキー階層]]における'''タイプ-0'''言語に相当する。全ての帰納的可算言語は[[複雑性クラス]] '''[[RE (計算複雑性理論)|RE]]''' に属する。

== 定義 ==
帰納的可算言語には以下の3つの等価な定義がある。

# 帰納的可算言語は、[[形式言語]]の[[アルファベット]]から生成可能な全ての単語の[[集合]]のうち、[[帰納的可算集合|帰納的可算]]な[[部分集合]]である。
# 帰納的可算言語は、その言語に含まれる全文字列を数え上げる[[チューリング機械]]（または[[計算可能関数]]）が存在する形式言語である。言語が無限である場合、同じ文字列が現れないようなアルゴリズムが必要である。すなわち、''n'' 番目の文字列が以前に出現しているかどうかを判定し、もし既出であったら ''n+1'' 番目の文字列を代わりに出力する。ただし、その ''n+1'' 番目の文字列も既出でないか確認が必要である。
# 帰納的可算言語は、入力された文字列がその言語に含まれる場合にそれを受理して停止するチューリング機械（または計算可能関数）が存在する形式言語である。ただし、入力された文字列がその言語に含まれない場合、停止して拒絶するかもしれないし、無限ループするかもしれない。[[帰納言語]]は常にチューリング機械が停止する点が異なる。

全ての[[正規言語]]、[[文脈自由言語]]、[[文脈依存言語]]、[[帰納言語]]は帰納的可算言語である。

'''RE''' とその補問題 co-'''RE''' は[[算術的階層]]の基盤となっている。

== 閉包属性 ==
帰納的可算言語は以下の操作について[[生成 (数学)|閉じている]]。すなわち、''L'' と ''P'' を2つの帰納的可算言語としたとき、以下の言語も同様に帰納的可算言語である。
* ''L'' の[[クリーネ閉包]] <math>L^*</math>
* ''L'' と ''P'' の連結 <math>L \circ P</math>
* [[合併 (集合論)|和集合]] <math>L \cup P</math>
* [[共通部分 (数学)|共通部分]] <math>L \cap P</math>

帰納的可算言語は[[差集合]]や補集合の操作については閉じていない。差集合 ''L''\''P'' や ''L'' の補集合は帰納的可算言語となる場合もあるし、ならない場合もある。

== 関連項目 ==
*[[帰納言語]]

== 外部リンク ==
* [https://complexityzoo.uwaterloo.ca/Complexity_Zoo:R#re Complexity Zoo: RE]

== 参考文献 ==
* Sipser, M. (1996), ''Introduction to the Theory of Computation'', PWS Publishing Co.
* Kozen, D.C. (1997), ''Automata and Computability'', Springer.

{{DEFAULTSORT:きのうてきかさんけんこ}}
[[Category:数理論理学]]
[[Category:形式言語]]
[[Category:計算理論]]
[[Category:数学に関する記事]]