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.

• I'm not convinced that $L_2$ is decidable. What makes you say that it is? Feb 12, 2013 at 12:42
• That's a question from a past test, the correct answer claims that, maybe it's wrong. Feb 12, 2013 at 12:45
• but still, when you see a question like that, how do you approach it? Feb 12, 2013 at 12:46
• Well, this isn't a brilliant answer, but, when we say decidable (I assume) we mean recursive. By recursive we mean that we can decide membership of the language so for $L_1$ you try to figure out if you can construct an algorithm that takes TM's as input and outputs yes if they are in $L_1$ or no if not. With $L_2$ you do something similar with DFA's. If you think you can't construct an algorithm and it may be undecidable then you try to reduce it to a problem which you already know to be undecidable. Feb 12, 2013 at 12:51
• curious, what level of a class was the test? undergraduate? which year? etc
– vzn
Feb 13, 2013 at 6:14

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.

• For an arbitrary $M_0$ and the promise that $L(M_0)$ is regular one cannot find $A_{M_{0}}$ though, so doesn't $A_{M_{0}}$ have to be part of the input? Feb 12, 2013 at 13:09
• Oh, no. I see my mistake. $M_0$ is fixed, so there exists an $A_{M{_0}}$ and there exists an algorithm deciding membership, you just can't obtain it for arbitrary $M_0$. Feb 12, 2013 at 13:11
• suspect $L_2$ is more subtle than that. if you have a TM that recognizes a regular language, how do you extract the DFA from that TM? suspect that could be hard or undecidable....? imagine for example the TM takes a very long time to accept or reject some words etc? thinking out loud... it is computable if there is a time or space limit, but otherwise, suspect it is uncomputable. this might be a good question for tcs.se?
– vzn
Feb 13, 2013 at 6:09
• @vzn: you don't have to extract it, you simply know that 1) if $L(M_0)$ is not regular $L_2 = \emptyset$ is decidable, 2) if it is regular then $A_{M_0}$ exists (you cannot calculate it automatically because "generating a regular language" is a nontrivial property and you can apply Rice's theorem again) but nevertheless $L_2$ is still decidable.
– Vor
Feb 13, 2013 at 8:02
• dont think so. $L_2$ is decidable if $A_{M_0}$ is given, but it is not given. if $L_2$ is decidable then it should be possible to exhibit (construct) the TM that decides it. right? but it is not. (if further restrictions on $M_0$ are given, ie time/space limits, it might be possible.)
– vzn
Feb 13, 2013 at 16:00

just looked this up in Hopcroft/Ullman, Introduction to Automata Theory, Languages, and Computation. $L_2$ seems to reduce to the question "is $L=R$ where $R$ is a given regular set?". on p281 the table states this is undecidable if $L$ is an r.e. set, ie recursively enumerable, ie a TM.