[Solved]: Intuition about decidability

Problem Detail: 

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.

Asked By : user6836

Answered By : Vor

For the first undecidable language $L_1$ you can apply the Rice's theorem:

Theorem (Rice's Theorem): Let L be a language of the form

$L = \{ \langle M \rangle | L(M)\mbox{ has some property }P\}$,where

1. P 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$.
2. 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.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/9703

3.2K people like this

 Download Related Notes/Documents