# Suppose $L_1, L_2, …, L_k$ are recursively enumerable languages forming a partition of $\Sigma^*$. How do I show that each $L_i$ are recursive?

Suppose $L_1, L_2, ..., L_k$ are recursively enumerable languages forming a partition of $\Sigma^*$.

How do I show that each $L_i$ are recursive ?

I see that for $x \in \Sigma^*$, $x$ belongs to exactly one $L_i$.

My idea is to run every Turing machine simultaneosly, stopping as soon as one of them accepts $x$ (must happen at some definite time by assumption).

What theory can I use to make my idea rigorous ? I've considered an non-deterministic TM, but also a $k$-tape TM, but none seems to suit my needs ?

Can someone help ?

• Then, yes, your approach is correct. What holds you from proving it rigorously? – Ran G. Sep 7 '15 at 8:26
• How do I run all Turing machines concurrently? I can't run them in series. I must have misunderstood either how k-tape or nondeterministic TM works. – Shuzheng Sep 7 '15 at 8:40
• look for dove-tailing, either in this site, or google. – Ran G. Sep 7 '15 at 8:44
• To realize dove-tailing in a Turing machine, you basically simulate one step of each machine in a round-robin manner, maintaining the current tape contents for each in a separate block on your tape. Note that the simulation my then involve moving these blocks when one needs more space. – Klaus Draeger Sep 7 '15 at 11:16

If you already proved the binary case, a more formal answer is to observe that, for any i, the complement of $L_i$ is r.e. since it is a finite union of r.e. sets. Since the set and its complement are r.e., it is recursive.