[解決済み] チューリングデシダブルとコ・チューリングデシダブルの違い

質問

この2つの違いを理解するのにとても苦労しています。 私の教科書では、基本的に次のように違いが説明されています。

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

この定義で私が理解できないのは、「チューリング認識可能な言語の補集合であるとはどういうことか」ということですね。

他の言語の補語であるかどうかは、具体的にどのように判断するのですか？

どのように解決するのか？

(注意："Turing decidable" と "co-Turing decidable" という用語は同じものである。 しかし、"Turing-recognizable" と "co-Turing-recognizable" は同じではないので、私の回答ではこれを取り上げることにしました。 その理由は、ある言語が決定可能であるならば、その補数も決定可能でなければならないからです。 認識可能な言語には同じことは当てはまりません)。

直感的には、言語内の文字列が与えられたとき、その文字列が本当にその言語内にあることを確認できるコンピュータ・プログラムがあれば、その言語はチューリング認識可能である、と言える。 このプログラムは、文字列が言語内にない場合は無限にループするかもしれないが、言語内の文字列を与えれば必ず最終的に受け入れることが保証されている。

チューリング認識可能な言語の補集合である場合、その言語はチューリング認識可能であることは事実ですが、この定義では何が起こっているのかがよくわかりません。 直感的には、ある言語が協調チューリング認識可能である場合、それは、文字列 ない その文字列がその言語にないことを最終的に確認する。 しかし、その文字列が本当に言語内にある場合は、無限にループする可能性がある。 ある文字列wがチューリング認識可能な言語に含まれていない場合、その文字列wはチューリング認識可能な言語の補集合に含まれているはずです（定義上）。 wはチューリング認識可能な補集合に含まれるので、wが本当に補集合に含まれることを確認できる何らかのプログラムが存在するはずである。 したがって、このプログラムは、wが元の協調チューリング認識可能言語にないことを確認できる。

要するに、チューリング認識可能性とは、ある文字列wがある言語の中にあることを確認できるプログラムが存在することであり、共同チューリング認識可能性とは、ある文字列wが、ある言語の中にあることを確認できるプログラムが存在することである。 ない を言語化した。

お役に立てれば幸いです。