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!
Best Answer
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.