Decidability of Recursively Enumerable Languages

1.6k Views Asked by At

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.

1

There are 1 best solutions below

0
On

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