再帰言語

数学、論理学、コンピュータサイエンスにおいて、形式言語（固定されたアルファベットから取られた有限の記号列の集合）は、その言語のアルファベット上のすべての可能な有限列の集合の再帰的部分集合である場合に再帰的と呼ばれる。同様に、有限の記号列を入力として与えられたときに、それが言語に属する場合は常に停止して受け入れ、そうでない場合は停止して拒否するチューリングマシンが存在する場合、形式言語は再帰的である。理論コンピュータサイエンスでは、このような常に停止するチューリングマシンは、全チューリングマシンまたはアルゴリズムと呼ばれる。^[1]再帰言語は決定可能とも呼ばれる。

決定可能性の概念は、他の計算モデルにも拡張できます。たとえば、非決定性チューリング マシンで決定可能な言語について話すことができます。したがって、あいまいさが生じる可能性がある場合は常に、「再帰言語」の同義語として、単に決定可能ではなく、チューリング決定可能言語が使用されます。

すべての再帰言語のクラスはRと呼ばれることが多いですが、この名前はRPクラスにも使用されます。

このタイプの言語はチョムスキー階層では定義されていません。^[2]すべての再帰言語は再帰的に列挙可能です。すべての正規言語、文脈自由言語、文脈依存言語は再帰的です。

再帰言語の概念には、同等な 2 つの主要な定義があります。

1. 再帰的形式言語は、言語のアルファベット上のすべての可能な単語の集合の再帰的な 部分集合です。
2. 再帰言語とは、有限の入力文字列が与えられたときに、その文字列が言語内にある場合は停止して受け入れ、そうでない場合は停止して拒否するチューリング マシンが存在する形式言語です。チューリング マシンは常に停止します。これは決定器として知られ、再帰言語を決定すると言われています。

2 番目の定義によれば、すべての入力で終了するアルゴリズムを示すことによって、任意の決定問題が決定可能であることが示されます。決定不可能な問題とは、決定できない問題のことです。

上で述べたように、すべての文脈依存言語は再帰的です。したがって、再帰言語の簡単な例は集合L={abc, aabbcc, aaabbbccc, ...}です。より正式には、集合

${\displaystyle L=\{\,w\in \{a,b,c\}^{*}\mid w=a^{n}b^{n}c^{n}{\mbox{ ある }}n\geq 1\,\}}$

コンテキストに依存するため、再帰的です。

文脈依存でない決定可能言語の例は、記述するのがより困難です。そのような例の 1 つを説明するには、数学的論理に関するある程度の知識が必要です。プレスブルガー算術は、加算を伴う（乗算は伴わない）自然数の 1 階理論です。プレスブルガー算術の適切な式の集合は文脈自由ですが、プレスブルガー算術の真のステートメントの集合を受け入れるすべての決定性チューリングマシンは、最悪の場合の実行時間が、ある定数c >0 に対して少なくとも になります。^[3]ここで、n は与えられた式の長さを示します。すべての文脈依存言語は線形制限オートマトンによって受け入れることができ、そのようなオートマトンはある定数cに対して最悪の実行時間で最大 の決定性チューリングマシンによってシミュレートできるため^{[出典が必要]}、プレスブルガー算術の有効な式の集合は文脈依存ではありません。良い面としては、 nの3倍の指数関数の時間で実行され、プレスブルガー算術の真の式の集合を決定する決定論的チューリングマシンが存在することが知られています。^[4]したがって、これは決定可能だが文脈に依存しない言語の例です。 ${\displaystyle 2^{2^{cn}}}$${\displaystyle c^{n}}$

再帰言語は、次の操作に対して閉じています。つまり、LとPが 2 つの再帰言語である場合、次の言語も再帰的です。

• クリーネ星 ${\displaystyle L^{*}}$
• 電子自由準同型φによる像 φ(L)
• 連結${\displaystyle L\circ P}$
• 組合${\displaystyle L\cup P}$
• 交差点${\displaystyle L\cap P}$
• の補数${\displaystyle L}$
• セット差${\displaystyle LP}$

最後の特性は、集合の差が交差と補集合で表現できるという事実から生じます。

• 再帰的に列挙可能な言語
• 計算可能な集合
• 再帰

• チョムスキー、ノーム（1959）。「文法の特定の形式的性質について」。情報と制御。2 （2）：137-167。doi ：10.1016 / S0019-9958（59）90362-6。
• フィッシャー、マイケル J. ;ラビン、マイケル O. ( 1974)。「プレスブルガー算術の超指数的複雑性」。応用数学における SIAM-AMS シンポジウムの議事録。7 : 27–41。
• Oppen, Derek C. (1978). 「プレスブルガー算術の計算量に関する222pnの上限」J. Comput. Syst. Sci . 16 (3): 323–332. doi : 10.1016/0022-0000(78)90021-1 .
• シプサー、マイケル(1997)。「決定可能性」。計算理論入門。PWS 出版。pp. 151–170。ISBN 978-0-534-94728-6。