# Decidability of Recursively Enumerable Languages

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.

• 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. – Andrés E. Caicedo Mar 4 '14 at 7:24
• (This is far from efficient in many cases. We have no way of anticipating how long we will have to wait.) – Andrés E. Caicedo Mar 4 '14 at 7:26

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}$.