World's most popular travel blog for travel bloggers.

Prove L and {0,1}*-L are recursively enumerable

, , No Comments
Problem Detail: 

Exercise ask : Prove which a binary language L is recursive if and only if both L and {0, 1}* - L are recursively enumerable.

Now I try to give a solution: Suppose that L is recursively enumerable.Then, would exist two machines M and M' such that simulate M and M' at alternate steps on two copies of the input x. For all the x that belong to A*({0-1}), at least one of the two machines M and M' would stop given that x € L xor x € A - L. If M' would stop then M" decide as M' while if M would stop then M" contradict M. It would follow that M" decide A*-L in contradiction with hypothesis.

Help me, I don't understand almost nothing on this part,I have a prof. incompetent, he has teach much bad with little theory and zero exercises.

Asked By : user47845
Answered By : Yuval Filmus

In one direction (the one you don't mention) this is easy. If $L$ is recursive then $L$ is recursively enumerable since we can go over all possible strings $x$, for each of them check whether $x \in L$, and output those which satisfy $x \in L$. A similar approach enumerates $\overline{L}$.

For the other direction, suppose you have a machine $A$ enumerating $L$ and another machine $B$ enumerating $\overline{L}$, and we want to construct a machine deciding $L$. Here is what we do. On input $x$, we run the machines $A$ and $B$ "in parallel", and observe the strings that they output. Eventually one of them outputs $x$. If $A$ output $x$, then $x \in L$; if it was $B$, then $x \notin L$.

The Turing machine model is sequential, so how do we run $A$ and $B$ in parallel? We simulate one step of $A$. Then we simulate one step of $B$. Then we simulate one step of $A$. Then we simulate one step of $B$. And so on. The result is as if we ran $A$ and $B$ in parallel. (This is very similar to how parallel threads are simulated on a single core; the main difference is that to improve efficiency, we run each of the threads many steps at a time.)

Best Answer from StackOverflow

Question Source :

3200 people like this

 Download Related Notes/Documents


Post a Comment

Let us know your responses and feedback