チューリングマシン M1、M2、M3 が存在し、それらが認識する言語はそれぞれ L(M1)、L(M2)、L(M3) であるとします。次の言語 L = {(M1, M2, M3) : L(M1), L(M2), L(M3) は等しくない} 言語は決定可能ですか? 再帰的に列挙可能？それともどちらでもない？
1205 次
1 に答える
2
M M i、Iを、入力で他のマシンM iの実行をシミュレートし、M iが最終的に停止した場合Iに戻り、それ以外の場合は永久にループするマシンとします。trueI
M∞を単純に永久にループする些細なマシンとします。
次に、（M M i 、 I、M∞、M∞）は、Miが入力で停止する場合にLになります。I
これにより、停止問題の決定可能性がLの決定可能性に減少するため、Lは決定不可能です。
=============
次に、Lが矛盾によって帰納的可算ではないことを証明しましょう。
Lが帰納的可算であると仮定すると、M i、M j、およびM kがそれぞれの言語が等しくない3つのチューリングマシンである場合、Mは最終的にトリプル（M i、M j、M k）。
ここで、Mを取得し、値（M、M'、M'）をL（M'）に追加することによって定義される、M'と呼ばれるMへの変更について考えてみましょう。重要な質問は、（M、M'、M'）がLにあるかどうかです。（M、M'、M'）がLにある場合、L（M）はL（M'）と等しくてはなりません（そうでない場合、Lにある定義に適合しません）。したがって、L（M） （M、M'、M'）を含めないでください（これが私たちが行った唯一の変更であるため）。逆に、（M、M'、M'）がLにない場合、L（M）！= L（M'）（L（M'）にそのトライプを追加したため）、したがって、Lにある必要があります（M）、言語が等しくないからです。
したがって、Mは存在できないことを意味するパラドックスに到達しました。したがって、Lは帰納的可算ではありません。
于 2012-03-10T06:35:36.213 に答える