4
$\begingroup$

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.

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

2 Answers 2

Reset to default
6
$\begingroup$

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.

Improve this answer
$\endgroup$
9
  • $\begingroup$ 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? $\endgroup$
    – Sam Jones
    Commented Feb 12, 2013 at 13:09
  • $\begingroup$ 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$. $\endgroup$
    – Sam Jones
    Commented Feb 12, 2013 at 13:11
  • $\begingroup$ 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? $\endgroup$
    – vzn
    Commented Feb 13, 2013 at 6:09
  • 2
    $\begingroup$ @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. $\endgroup$
    – Vor
    Commented Feb 13, 2013 at 8:02
  • $\begingroup$ 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.) $\endgroup$
    – vzn
    Commented Feb 13, 2013 at 16:00
0
$\begingroup$

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.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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