-1
$\begingroup$

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.

$\endgroup$

closed as unclear what you're asking by D.W., Juho, André Souza Lemos, Luke Mathieson, Tom van der Zanden Jul 2 '15 at 6:55

Please clarify your specific problem or add additional details to highlight exactly what you need. As it's currently written, it’s hard to tell exactly what you're asking. See the How to Ask page for help clarifying this question. If this question can be reworded to fit the rules in the help center, please edit the question.

  • 1
    $\begingroup$ You seem to understand the general idea, but you have to improve the presentation of your proofs.. You should be careful to give the definition of all the symbols you use. For example, in your proof, you give nowhere the definition of A or of M". Another point is that there is no need for contradiction in the proof. $\endgroup$ – babou Jun 27 '15 at 20:37
  • 1
    $\begingroup$ What is your question? I see a bunch of declarative statements, but I don't see any question. If the question is: "please check whether my solution is correct", that is off-topic for this site, as our site policy says that "please check my solution" questions are not suitable here. See meta.cs.stackexchange.com/a/722/755. $\endgroup$ – D.W. Jun 28 '15 at 4:33
  • 1
    $\begingroup$ In addition to what D.W. writes, flaming over your instructor is out of place here. $\endgroup$ – Raphael Jun 28 '15 at 9:24
2
$\begingroup$

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.)

$\endgroup$

Not the answer you're looking for? Browse other questions tagged or ask your own question.