Mは、私は、この言語が認識可能であるかどうかを証明する必要がWの文字列を受け入れ、

Question

ε文字列を受け付けないチューリングマシンである：

{＆langle、M、W＆rangle ;: Mは、チューリングマシンであります文字列wを受け入れ、私は _TMの削減を行うことができます理解が、どのように私は空の文字列を処理しない文字列ε}

を受け入れていませんか？

Answer 1

あなたの言語にA _TMの補数を減らす方法の1つです。 TM Mと、このTM /文字列のペアを構築し、Wの文字列が与えられ

：

M' = "On input x: 
     If x = "iheartquokkas", accept. 
     Otherwise: 
      Run M on w. 
      If M accepts, accept; 
      If M rejects, reject; 
      (Implicitly: if M loops, loop.)" 
w' = "iheartquokkas" 

まず、MはWを受け入れないこととします。それで、マシンM 'は実際にそれをプログラムするので、文字列w'を受け入れます。さらに、M＆apos;を実行すると、Mはwで実行され、Mはwを受け入れないため、決して受け入れません。したがって、M 'はw'を受け入れるがεは受け入れないので、M '、w'＆rangle;あなたの言語です。

第2に、Mがwを受け入れるとします。それでM＆aを実行すると、それは受け入れられるので、M 'はw'を受け入れるが、εは受け入れない。したがって、M '、w'あなたの言語ではありません。

あなたの言語にA _TMの補数がマッピングされました。あなたの言語は認識できません。

今、あなたはそれが共存できないことを証明できますか？