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.
Prove L and {0,1}*-L are recursively enumerable
computability;turing machines
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.)