theory - Turing-Decidable と Co-Turing-Decidable の違い

Question

私はこれら2つの違いを理解するのに本当に苦労しています。私の教科書から、それは本質的に次のように違いを説明しています

言語がチューリング認識可能な言語の補数である場合、その言語は共チューリング認識可能です。

私が理解していないこの定義の部分は、チューリング認識可能な言語の補完である場合、それはどういう意味ですか?

それが別の言語の補数であるかどうかをどのように正確に判断しますか?

Answer 1

(注 - 「チューリング決定可能」と「共同チューリング決定可能」という用語は同じものです。しかし、「チューリング認識可能」と「共同チューリング認識可能」は同じではなく、私が決めたのはこれです)この理由は、言語が決定可能である場合、その補語も決定可能でなければならないからです.認識可能な言語については同じではありません.)

直観的に、その言語の文字列が与えられたときに、その文字列が実際に言語内にあることを確認できるコンピューター プログラムがあれば、その言語はチューリング認識可能です。文字列が言語にない場合、このプログラムは無限にループする可能性がありますが、言語に文字列を指定すると、常に最終的に受け入れることが保証されています。

言語がチューリング認識可能な言語の補語である場合、その言語が共同チューリング認識可能であることは事実ですが、この定義は何が起こっているのかをあまり明らかにしていません。直観的に、言語が共チューリング認識可能である場合、それは文字列が与えられた場合にそうでないコンピューター プログラムがあることを意味します。言語で、最終的に文字列が言語にないことを確認します。ただし、文字列が実際に言語内にある場合は、無限にループする可能性があります。この理由は単純です。ある文字列 w が共同チューリング認識可能な言語に含まれていない場合、その文字列 w は、その共同チューリング認識可能な言語の補数に含まれている必要があります。チューリング認識可能であること。w はチューリング認識可能な補数に含まれているため、w が実際に補数に含まれていることを確認できる何らかのプログラムが必要です。したがって、このプログラムは、w が元の共チューリング認識可能な言語ではないことを確認できます。

つまり、チューリング認識可能性とは、文字列 w がその言語にあることを確認できるプログラムがあることを意味し、共チューリング認識可能性とは、文字列 w がその言語にないことを確認できるプログラムがあることを意味します。

お役に立てれば！

Answer 2

その言語の文字列のみを停止して受け入れるチューリング マシンが存在する場合、その言語は認識可能であり、その言語にない文字列の場合、TM は拒否するか、まったく停止しません。注: チューリング マシンが言語に含まれていない文字列に対して停止する必要はありません。

言語内の文字列を受け入れ、言語内にない文字列を拒否するチューリング マシンが存在する場合、その言語は決定可能です。