言語の決定可能性

すべての入力文字列 w を受け入れて停止するチューリングマシンがある場合、言語は Decidable または Recursive と呼ばれます。すべての決定可能な言語はチューリング対応です。

*P* に対するすべてのyesインスタンスの言語 *L* が決定可能であれば、決定問題 *P* は決定可能です。

決定可能な言語の場合、入力文字列ごとに、TMは次の図に示すように、受け入れ状態または拒否状態のいずれかで停止します-

例1

次の問題が決定可能かどうかを調べます-

数は「m」素数ですか？

素数= \ {2、3、5、7、11、13、…………..}

「2」から始まる「2」から「√m」までのすべての数字で、数字の「m」を割ります。

これらの数値のいずれかが剰余ゼロを生成する場合、「拒否状態」になります。それ以外の場合、「受け入れ状態」になります。したがって、ここで答えは「はい」または「いいえ」で作成できます。

したがって、それは決定的な問題です。

通常の言語 L と文字列 w が与えられた場合、 w∈L かどうかをどのように確認できますか？

*L* を受け入れるDFAを受け取り、 *w* が受け入れられるかどうかを確認します

いくつかの決定可能な問題があります-

注-