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

Question

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}

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