# Determining if a language is Recursively Enumerable

Here is a problem from John Hopcroft's "Introduction to Automata Theory" that I'm having a hard time trying to understand.

Exercise 9.2.5: Let L be recursively enumerable and let Overscript[L, _] be non-RE. Consider the > language:

L' = {0w | w is in L} $\cup$ { 1w | w is not in L }

Can you say for certain whether L' or its complement are recursive, RE, or non-> RE? Justify your answer:

"Note that the new language defined in the displayed text should be L'; it is > > different from the given language L, of course. Also, we'll use -L for the > > complement of L in what follows. Suppose L' were RE. Then we could design a TM M for -L as follows. Given input w, M changes its input to 1w and simulates the hypothetical TM for L'. If that TM > accepts, then w is in -L, so M should accept. If the TM for L' never accepts, > then neither does M. Thus, M would accept exactly -L, which contradicts the fact > that -L is not RE. We conclude that L' is not RE."

and here is what I don't get:

..."Thus, M would accept exactly -L, which contradicts the fact that -L is not RE"....

Why? M is the Turing Machine for -L, so it is supposed to accept -L, right?

If we can construct a Turing Machine for a language, then it is RE. We have constructed a TM for something we know is not RE (-L), based on the TM for the supposedly RE L'. So what? how does this leads to the conclusion that L' is not RE? I'm very confused...

Any help will be much appreciated

Thanks!

-
It was assumed that the complement of $L$ is not r.e. – André Nicolas Jun 15 '12 at 21:06

The hypothesis of the exercise is that $L$ is RE and $-L$ is not RE. The argument is that if $L'$ were RE, then $-L$ would also be RE, contradicting this hypothesis.
$L'$ is not c.e. If $L'$ was c.e., then you can enumerate computably all the elements of $L'$. From this computable enumeration of $L'$, you can make an enumeration of $\overline{L}$ as follows: in the enumeration of $L'$, if you see a string enumerated that starts with $1$ of the form $1w$, then put $w$ into the enumeration of $\overline{L}$. This gives an enumeration of $\overline{L}$, so $\overline{L}$ is c.e. Contradicting the assumption. Since $L'$ is not c.e., it can not be computable.
Note that $-L' = \{0w : w \notin L\} \cup \{1w : w \in L\}$. Apply the same argument to $-L'$ to conclude it is not c.e.