turing-machines - すべての無限言語は決定不能ですか?

Question

無限の言語はすべて決定不可能なのだろうか?

TM が無限の言語を決定しようとすると、永久にループするため、決定者ではなく認識者になるため、それらは正しいに違いありません。

みんなありがとう。

Answer 1

いいえ、決定可能な言語は無限にあります。些細な例の 1 つは language です{n € N | a^n}。つまり、文字 "a" のみを含む単語の言語です。この言語は正規表現で照合できますa*。したがって、それは正規言語であり、したがって決定可能です。

Answer 2

sepp2k が指摘するようにa*、正規言語であるため、決定可能です。

すべての有限言語は正則です。いくつかの無限言語は規則的です。決定不能になるのは無限の言語だけです。

判断できないようにするには、TM が失敗する原因となる個々の文字列が言語に存在する必要があります。実際、そのような文字列は無数に存在するはずです (そうでない場合、動作の悪い文字列は特殊なケースのロジックで処理される可能性があります)。

したがって、言語が無限であるということは、決定不能性にとって必要ですが、十分ではありません。