Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

Thanks!

share|improve this question
1  
It was assumed that the complement of $L$ is not r.e. –  André Nicolas Jun 15 '12 at 21:06
add comment

2 Answers

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|improve this answer
add comment

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|improve this answer
add comment

Your Answer

 
discard

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.