$ALL_{TM} = \{\langle M\rangle | \; M$ is $TM$ and $L(M)=\Sigma^*\}$
$E_{TM} = \{\langle M\rangle | \; M$ is $TM$ and $L(M)=\emptyset\}$

I can't find reduction of $ALL_{TM}$ to $E_{TM}$. But I can't proof that it does not exist. Is there is such a reduction?


The point to note is if you can reduce $L_1$ to $L_2$ then the same reduction/mapping can be used to see that $\overline{L_1}$ is reducible to $\overline{L_2}$. The following is the proof, avoid if you just needed the hint.
Now we know $E_{TM}$ is not Turing recognizable but $\overline{E_{TM}}$ is. Secondly we know $\overline{ALL_{TM}}$ is not Turing recognizable . So say if $ALL_{TM}$ is reducible to $E_{TM}$, then it would mean $\overline{ALL_{TM}}$ is reducible to $\overline{E_{TM}}$, and as $\overline{E_{TM}}$ is Turing recognizable $\overline{ALL_{TM}}$ would become Turing recognizable which is a contradiction.

  • $\begingroup$ Yes other moderators told me that. I was ready to remove my answer but it was decided that in future I should not post answers to questions directly asking for solutions. Now I take care of it. $\endgroup$
    – sashas
    Jan 26 '16 at 17:22
  • $\begingroup$ Okay, never mind then. :) (Please flag this for removel after reading. Thanks!) $\endgroup$
    – Raphael
    Jan 26 '16 at 23:51

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.