何も受け入れないチューリングマシンは再帰的に列挙できません。

Question

何も受け入れないチューリングマシンは再帰的に列挙できません。

Answer 1

何も受け入れないチューリングマシンのエンコーディングの言語は、再帰的に列挙できないことを示すために、間接的な引数を使用します。

補題1：Lとその補数が再帰的に列挙可能であれば、Lは再帰的です。

証明：MはLとM」は任意の文字列sを考えるとL.の補数を列挙TMも列挙TMなりましょうが、我々は次のようにsがLであるかどうかを決定することができます。 MとM 'の実行を開始し、各実行が最終的に任意の実行時間を得るように実行をインタリーブします。 sがLの場合、Mは最終的にそれをリストします。その時点で、sはLであり、停止します。 sがL内にない場合、M 'は最終的にそれをリストし、その時点でsがL内にないことを知り、停止する。したがって、任意のsについて、sが停止している場合は受け入れるか、そうでない場合は停止することができます。したがって、Lとその補数は再帰的です。

補題2：何かを受け入れるチューリングマシンのエンコーディングの言語は、再帰的に列挙できます。

プルーフ：すべてのチューリングマシンエンコーディングのセットがカウント可能であり、すべての可能なテープ入力のセットもカウント可能です。したがって、機械と入力の組の集合（M、s）は数えられる。したがって、これらのペアp1、p2、...、pk、...のいくつかの順序を仮定することができる。各ペアp =（M、s）に対して、入力sに対してマシンMを実行し、ペアp1、 ...、pk、...それぞれは最終的に任意の量のランタイムを取得します。 pkがhalt-accept状態になると、Mを何かを受け入れるTM（すなわち、対応するs）として直ちにリストすることができ、同じMをチェックしている他の実行中のインスタンスをすべて終了することもできます。何らかの入力を受け入れるすべてのマシンMが最終的に起動され、最終的には入力に対して受け入れられるので、すべてのマシンが最終的に列挙されます。

補題3：何も受け入れないチューリングマシンのエンコーディングの言語は再帰的ではありません。

証明書：これは、Riceの定理の直接的な結果です。プロパティ "accepts nothing"は言語そのものの意味属性であり、すべてではない言語の一部には当てはまります。従って、TMは、他のTMがそのプロパティを有する言語を受け入れるか否かを決定することはできない。

定理：何も受け入れないチューリングマシンのエンコーディングの言語は、再帰的に列挙できません。

証明書：この言語は再帰的に列挙可能であると仮定します。補題2では補題が再帰的に列挙できることがすでに証明されています。補助定理1によれば、両方の言語は再帰的である。しかしながら、補題3は、言語が再帰的でないことを証明する。これは矛盾です。唯一の仮定は、言語が再帰的に列挙可能であったため、仮定は偽であったに違いありません。したがって、言語は再帰的に列挙できません。