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.

Was it helpful?

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

Licensed under: CC-BY-SA with attribution
Not affiliated with cs.stackexchange
scroll top