Take the 2-minute tour ×
Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It's 100% free, no registration required.

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.

share|improve this question
    
I'm not convinced that $L_2$ is decidable. What makes you say that it is? –  Sam Jones Feb 12 '13 at 12:42
    
That's a question from a past test, the correct answer claims that, maybe it's wrong. –  user6836 Feb 12 '13 at 12:45
    
but still, when you see a question like that, how do you approach it? –  user6836 Feb 12 '13 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. –  Sam Jones Feb 12 '13 at 12:51
    
curious, what level of a class was the test? undergraduate? which year? etc –  vzn Feb 13 '13 at 6:14
add comment

2 Answers

up vote 6 down vote accepted

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.

share|improve this answer
    
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? –  Sam Jones Feb 12 '13 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$. –  Sam Jones Feb 12 '13 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 '13 at 6:09
2  
@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 '13 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 '13 at 16:00
show 4 more comments

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.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.