Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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:

Here is the oficial 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


share|cite|improve this question
It was assumed that the complement of $L$ is not r.e. – André Nicolas Jun 15 '12 at 21:06
up vote 3 down vote accepted

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.

share|cite|improve this answer

I use the term c.e. for r.e. and computable for recursive.

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

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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