0
$\begingroup$

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.

$\endgroup$
0
$\begingroup$

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

$\endgroup$

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.