theory - チューリングマシンが受け入れられない既知の言語は?

Question

たとえば、独自のエンコーディングを受け入れないチューリング マシンの言語は、どのチューリング マシンでも受け入れることができません。

Answer 1

TMが決定できない言語は無限にあります。実際、「ほとんどの」言語は決定不可能です。数え切れないほど多くの決定可能な言語がありますが、数え切れないほど多くの言語があります（したがって、数え切れないほど多くの決定不可能な言語）。

ライスの定理により、決定不可能な言語の例をたくさん思いつくことができます。ウィキペディアのページを参照してください：ライスの定理

基本的に、自明ではない言語のセットがある場合（つまり、セット内の言語を認識するTMと、セット内にない言語を認識するTMがある場合）、任意のTMの言語がSにあるかどうかは決定できません。 。たとえば、Sを空の言語で構成されるセットとします。次に、任意のTMが空の言語を受け入れるかどうか、つまり文字列を受け入れないかどうかを判断することはできません。自明ではない言語のセットを考え出すと、新しい決定不可能な言語ができます（セット内の言語を認識するTMのすべてのエンコーディング）。