帰納的可算言語

帰納的可算言語について

帰納的可算言語（きのうてきかさんげんご）とは、形式言語の一種であり、計算機科学や数学、論理学において重要な概念です。このタイプの言語は、部分決定性言語やチューリング受理性言語としても知られ、形式言語のチョムスキー階層においてはタイプ-0言語に該当します。この言語の特性を理解することは、計算の基礎を学ぶ上で欠かせません。

定義

帰納的可算言語には、次の3つの等価な定義が存在します。

1. 部分集合としての定義：帰納的可算言語は、特定のアルファベットから生成される全単語集合の中で、帰納的に可算な部分集合です。

2. チューリング機械による生成：この言語に含まれる全ての文字列を数え上げることができるチューリング機械や計算可能関数が存在します。この場合、無限の文字列が存在する場合には、同一の文字列が再出力されないように、適切にアルゴリズムが構成される必要があります。具体的には、n 番目の文字列が既に出現しているかを判定し、新たに n+1 番目の文字列を選ぶという形です。

3. 受理機械の特性：入力された文字列がその言語に含まれている場合、その文字列を受理して計算が停止するチューリング機械が存在します。逆に、含まれていない場合は、拒絶するか無限ループする可能性があるのが特徴です。

なお、帰納的可算言語は全ての正規言語、文脈自由言語、文脈依存言語、そして全ての帰納言語を含んでいます。また、帰納的可算言語のクラスは、計算の基礎の一部となるREおよびその補問題であるco-REとの関連性を持っています。

閉包属性

帰納的可算言語は特定の演算に関して閉じた性質を持ちます。具体的には、2つの帰納的可算言語LとPに対し、以下の言語もまた帰納的可算言語として認められます：

• - L のクリーネ閉包：Lの全ての文字列を無限に連結した結果の集合、L。
• - L と P の連結：言語LとPの文字列を合わせた言語、L∘P。
• - 和集合：LとPに含まれる全ての文字列を集めた集合、L∪P。
• - 共通部分：LとPに共通する文字列のみを集めた集合、L∩P。

しかし、帰納的可算言語は差集合や補集合に関しては閉じていないことに注意が必要です。つまり、差集合Lackslash PやLの補集合が必ずしも帰納的可算言語となるわけではなく、場合によってはならないこともあります。

まとめ

計算機科学において帰納的可算言語は、その根本的な特性や操作に関して理解しておく必要があります。特に、帰納的可算言語の性質や定義を踏まえることで、より深い計算理論を学ぶための基盤が築かれます。関連するトピックとして、帰納言語や算術的階層についての研究も重要です。

参考文献

• - Sipser, M. (1996). Introduction to the Theory of Computation, PWS Publishing Co.
• - Kozen, D.C. (1997). Automata and Computability*, Springer.

もう一度検索