1
$\begingroup$

I'm having trouble with this problem, I know that every decidable language is recursively enumerable but that not every recursively enumerable language is decidable.

What are the steps involved in figuring out which recursively enumerable language is decidable?

Assume that E is an alphabet and that E* is partitioned into n disjoint languages L1, L2...,Ln. If they are recursively enumerable, show that they are also decidable.

$\endgroup$
  • $\begingroup$ For each $i$, you need an algorithm that always halts, and that with input a word in $E^*$, it has output YES iff the word is in $L_i$. The obvious approach is to run enumerations of all the $L_j$. eventually, your word will be listed in one of them. $\endgroup$ – Andrés E. Caicedo Mar 4 '14 at 7:24
  • $\begingroup$ (This is far from efficient in many cases. We have no way of anticipating how long we will have to wait.) $\endgroup$ – Andrés E. Caicedo Mar 4 '14 at 7:26
4
$\begingroup$

Hint: A set is decidable iff it and its complement are recursively enumerable.

| cite | improve this answer | |
$\endgroup$
1
$\begingroup$

I like Quinn Culver's answer. I want to expand on it though. A Language L is decidable if and only if L and $\overline{L}$ are both recursively enumerable. The proof of this is by simulation. Consider the string $\omega$. Let $M, \overline{M}$ be Turing Machines that accept $L, \overline{L}$ respectively. We simulate $M, \overline{M}$ on $\omega$. We know that $\omega$ is in exactly one of these sets. So at least one of the two Turing Machines will halt. If $M$ halts in the accepting state, $\omega \in L$. Otherwise, $\overline{M}$ will halt in the accepting state, which implies that $\omega \in \overline{L}$.

Decidable languages are closed under a few operations, such as set union, set intersection, set complementation, string concatenation, and Kleene closure. If you remember dealing with problems asking you to decide if a language is regular, the logic for decidability is quite similar.

The link below is a good resource to read some more on the topic.

http://www.dreamincode.net/forums/topic/338311-turing-machines-and-formal-languages/

Hope this helps some!

| cite | improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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