I have to prove that the language $L_2:=${$<M>$|$L(M)=\overline{A_TM}$} is (un-)decidable. In a previous assignment we proved that $L_1:=${$<M>$|$L(M)=A_TM$} is undecidable.

I would say that $L_1$ is decidable because we can build a decider S.

S="on input w": (rough outlined)

  1. breadth first search

    (a) if no accept state was found, accept

    (b) else reject

Am I wrong with my guess?

$\overline{A_TM}$={<M,w>|M is a TM and does not accept w}


1 Answer 1


For $L_1:$

It's not decidable.

Define $C=\{A_TM\}$. Now, by Rice's theorem we have that the language $L=\{<M>|L(M)\in C\}$ is undecidable. (By the extended theorem it's not even semi-decidable.)

But notice $L_1=L$ and therefore $L_1$ is undecidable.

For $L_2:$

It's decidable, although your solution is not correct.

Notice that $\overline{A_TM}$ is not semi-decidable, and therefore there is no TM $M$ where $L(M)=\overline{A_TM}$. Thus, $L_2=\{<M>|L(M)=\overline{A_TM}\}=\emptyset$ and thus a TM that always rejects will decide $L_2$.

  • $\begingroup$ I have now noticed i solved for $L_1$ and not $L_2$. I will add to the solution to it immediately $\endgroup$
    – nir shahar
    Jun 27, 2020 at 11:20
  • $\begingroup$ Semi-decidable just means, that there exists a TM M which have to stop for "yes" instances? So, not semi-decidable just means that M does not have to stop for "yes" instances? - We didn't had that topic in our lectures. $\endgroup$ Jul 18, 2020 at 16:11

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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