1
$\begingroup$

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 ?

$\endgroup$
  • 4
    $\begingroup$ Then, yes, your approach is correct. What holds you from proving it rigorously? $\endgroup$ – Ran G. Sep 7 '15 at 8:26
  • $\begingroup$ 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. $\endgroup$ – Shuzheng Sep 7 '15 at 8:40
  • 4
    $\begingroup$ look for dove-tailing, either in this site, or google. $\endgroup$ – Ran G. Sep 7 '15 at 8:44
  • 2
    $\begingroup$ 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. $\endgroup$ – Klaus Draeger Sep 7 '15 at 11:16
1
$\begingroup$

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.

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