finite-automata - 言語が決定可能であることを証明するとき、あなたは効果的に何をしていますか？

Question

言語が決定可能であることを証明するとき、あなたは効果的に何をしていますか？

Answer 1

どのように行われるのかと聞かれたら、よくわかりませんが、確認することはできます。

基本的に、決定可能性とは、（入力を受け入れるか拒否するかを問わず）任意の有限入力に対して停止するアルゴリズム（つまりチューリングマシン）を構築できる言語です。決定不能は、決定不可能な言語です。

http://en.wikipedia.org/wiki/Recursive_language ...しかし、この主題に関する詳細は簡単に見つけることができます。このリンクには、この用語についての簡単な言及しかありません。

psしたがって、上記のアルゴリズムを構築するときは、基本的に言語が決定可能であることを証明しています。