帰納言語

帰納言語について

帰納言語（Recursive language）は、数学や論理学、計算機科学における形式言語の重要な一群です。この言語は、決定される言語（Decidable Language）やチューリング決定性言語（Turing-decidable Language）とも呼ばれます。これらの言語が属する複雑性クラスをRと称し、RPクラスもRと呼ばれることがあります。注目すべき点は、帰納言語がチョムスキー階層内で明確に定義されていないことです（Chomsky 1959）。

定義

帰納言語は、以下の二つの等価な定義を持っています。第一に、帰納言語は形式言語のアルファベットによって構成される全単語の集合からなる帰納的な部分集合です。第二に、この言語に対して受容するチューリングマシンが存在する場合、帰納言語に属する文字列を入力すると常に停止して受容し、逆に属さない文字列を入力すると停止して拒絶するように設計されています。ここで言う「停止」とは、プログラムが完成することを意味します。このようなチューリングマシンは「decider」と呼ばれ、帰納言語の決定を行います。全ての帰納言語は、帰納的に枚挙可能であり、正規言語、文脈自由言語、文脈依存言語は全て帰納言語に含まれます。

閉包属性

帰納言語は、特定の操作に対して閉じており、例えば次のように定義されます。もし、L と Pが二つの帰納言語である場合、以下に挙げる言語もまた帰納言語となります:

1. Lのクリーネ閉包 (L*) – Lに含まれる全ての文字列を含む集合。
2. Lの準同型写像 (φ(L)) – Lの要素を特定の法則に従って変換した結果。
3. LとPの連結 (L ∘ P) – Lの要素に続いてPの要素がつながるように結合したもの。
4. 和集合 (L ∪ P) – LまたはPに属する全ての要素を含む集合。
5. 共通部分 (L ∩ P) – LとPの両方に同時に属する要素の集合。
6. Lの補集合 – Lに属さない要素全てを集めた集合。
7. 差集合 (L - P) – Lに属するがPには属しない要素の集合。

特に、差集合は和集合と共通部分から得られることに注意が必要です。これは、数学的な操作として非常に重要です。

参考文献

この分野における理論は、多くの研究や文献によって支えられています。特に、Michael Sipserの著書『Introduction to the Theory of Computation』 （1997年）や、Chomskyの「On certain formal properties of grammars」（1959年）が基礎を築く重要な資料です。

関連項目

帰納的可算言語や再帰呼び出し、再帰的頭字語など、帰納言語と密接に関連するテーマも多くあります。これらの概念は、計算理論の理解を深めるために不可欠です。

もう一度検索