再帰的に列挙可能な言語

数学、論理学、コンピュータサイエンスにおいて、形式言語は、その言語のアルファベット上のすべての可能な単語の集合において再帰的に列挙可能な部分集合である場合、すなわち、その言語のすべての有効な文字列を列挙するチューリングマシンが存在する場合、再帰的に列挙可能（または、認識可能、部分的に決定可能、半決定可能、チューリング受容可能、チューリング認識可能）であると呼ばれます。

再帰的に列挙可能な言語は、形式言語のチョムスキー階層ではタイプ 0言語として知られています。すべての正規言語、文脈自由言語、文脈依存言語、再帰言語は再帰的に列挙可能です。

すべての再帰的に列挙可能な言語のクラスはREと呼ばれます。

再帰的に列挙可能な言語には、同等の定義が 3 つあります。

1. 再帰的に列挙可能な言語とは、その言語のアルファベット上のすべての可能な単語の集合における再帰的に列挙可能な 部分集合のことです。
2. 再帰的に列挙可能な言語とは、言語のすべての有効な文字列を列挙するチューリング マシン(またはその他の計算可能な関数)が存在する形式言語です。言語が無限である場合、数値nに対して生成された文字列がn未満の数値に対して「すでに」生成されているかどうかをテストできるため、提供される列挙アルゴリズムは繰り返しを回避するように選択できることに注意してください。すでに生成されている場合は、代わりに入力n +1の出力を使用します(再帰的)。ただし、これが「新しい」かどうかを再度テストします。
3. 再帰的に列挙可能な言語とは、入力として言語内の任意の文字列が提示されたときに停止して受け入れるチューリング マシン (またはその他の計算可能な関数) が存在する形式言語です。ただし、言語にない文字列が提示されたときには停止して拒否するか、永久にループします。これを、チューリング マシンがすべてのケースで停止することを要求する再帰言語とは対照的です。

すべての正規言語、文脈自由言語、文脈依存言語、再帰言語は再帰的に列挙可能です。

ポストの定理は、 REとその補集合 co-RE が算術階層の第 1 レベルに対応することを示しています。

停止チューリングマシンの集合は再帰的に列挙可能ですが、再帰的ではありません。実際、チューリングマシンを実行してマシンが停止するかどうかを受け入れることができるため、再帰的に列挙可能です。一方、問題は決定不可能です。

再帰的ではないが再帰的に列挙可能な言語には、次のようなものがあります。

• 郵便対応の問題
• 死亡率（計算可能性理論）
• 結論問題

再帰的に列挙可能な言語 (REL) は、次の演算に対して閉じています。つまり、LとPが2 つの再帰的に列挙可能な言語である場合、次の言語も再帰的に列挙可能です。

• Lのクリーネ 星${\displaystyle L^{*}}$
• LとPの連結​ ${\displaystyle L\circ P}$
• 組合​ ${\displaystyle L\cup P}$
• 交差点。​ ${\displaystyle L\cap P}$

再帰的に可算な言語は、集合の差や補集合に関して閉じていません。が再帰的である場合、集合の差は再帰的に可算です。 が再帰的に可算である場合、 の補集合は、も再帰的である 場合に限り、再帰的に可算です。${\displaystyle LP}$${\displaystyle P}$${\displaystyle L}$${\displaystyle L}$ ${\displaystyle L}$

• 計算可能な列挙可能な集合
• 再帰

• Sipser, M. (1996)、「計算理論入門」、PWS Publishing Co.
• Kozen、DC (1997)、『Automata and Computability』、Springer。

• 複雑性動物園：クラス RE
• 講義スライド