Given a language, how do you go about deciding if it's decidable or not? For example:Given a DFA $A_0$ and a TM $M_0$$L_1 = \{ \langle M \rangle \, | \, M \mbox{ is a TM and }L(M) = L(A_0) \}$$L_2 = \{ \langle A \rangle \, | \, A \mbox{ is a DFA and }L(A) = L(M_0) \}$What's the intuition/process of figuring out if $L_1$, $L_2$ are decidable or not?This is not homework, $L_1$ is not decidable and $L_2$ is decidable, but I have not idea why, and how to solve this problem and problems similar to it. If you could explain to me the process of doing that you will help a lot.
Intuition about decidability
turing machines;undecidability
For the first undecidable language $L_1$ you can apply the Rice's theorem:Theorem (Rices Theorem): Let L be a language of the form$L = \{ \langle M \rangle | L(M)\mbox{ has some property }P\}$,whereP is non-trivial, i.e. there exist at least one machine M such that $\langle M \rangle \in L$, and at least one machine $M$ such that $\langle M \rangle \notin L$.P is indeed a property of the language of TMs, i.e. whenever $L(M_1) = L(M_2)$,we have $\langle M_1 \rangle \in L$ if and only if $\langle M_2 \rangle \in L$.Then L is undecidable.You can pick a Turing machine that decides $A_0$ and one that decides $\overline{A_0}$, so $L_1$ asserts a nontrivial property of $\langle M \rangle$, and so it is undecidable.For the second decidable language $L_2$ the machine $M_0$ is fixed (it is not part of the language).So $L(M_0)$ is regular or it is not regular. If it is not regular then $L_2 = \emptyset$ (trivially decidable). If $L(M_0)$ is regular then there is a DFA $A_{M_0}$ such that $A_{M_0} = L(M_0)$ and the language $L_2$ becomes:$L_2 = \{ \langle A \rangle | L(A) = L(A_{M_0}) \}$but the equivalence of two DFAs is decidable, so $L_2$ is decidable.