Help me understand this Turing-machine Problem concerning $A_{TM}$
-
29-09-2020 - |
Question
I'm a Physics/C.S. student and have been struggling with this particular problem for a few days now. So the task is as following:
Consider the following languages:
$\hspace{20pt} L_1 = \{\langle M \rangle \, | \, L(M) = A_{TM}\} \\ \hspace{20pt} L_2 = \{\langle M \rangle \, | \, L(M) = \overline{A_{TM}}\}$
Are these decidable? Prove your decision.
$A_{TM}$ is defined as $\{\langle M , w\rangle \, | \,\text{M is a TM and M accepts w}\}$
So first off I'm trying to understand the first language $L_1$. What exactly would it mean for $L_1$ to be decidable? I understand why $A_{TM}$ isn't decidable, but what would a TM that decides $L_1$ actually do?
I feel like I already know the solution to the second problem but would like to know whether my gut instinct is right. So since $\overline{A_{TM}}$ isn't Turing-recognizable it means that $M$ with $L(M) = \overline{A_{TM}}$ doesn't exist/is empty. Thus $L_2 = \emptyset$ and that's easily decidable.
Solution
Solving the language $L_1$ means knowing for every TM if it's semi-deciding the $A_{TM}$ problem.
Your instinct is right - it is empty and therefore decidable. If it wasn't empty by any chance, then by Rice's theorem it would have not been decidable