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}


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$.

| cite | improve this answer | |
  • $\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 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$ – Schleudergang Jul 18 at 16:11

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.