# Is $L_2:=${$<M>$|$L(M)=\overline{A_TM}$} (un-)decidable?

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

(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=\{|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=\{|L(M)=\overline{A_TM}\}=\emptyset$$ and thus a TM that always rejects will decide $$L_2$$.

• I have now noticed i solved for $L_1$ and not $L_2$. I will add to the solution to it immediately – nir shahar Jun 27 at 11:20
• 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. – Schleudergang Jul 18 at 16:11