If you want to make money online : Register now

$L \in RE$ Question

, , No Comments
Problem Detail: 

I see a sentence in one final exam on automaton course.

I have one problem: if we want to have a TM that halts for all word in L, it's enough to have L be R.E? or we should have R be R.E and Complement of R be R.E?

Note: (Recursive Enumerable = R.E).

Asked By : user3661613
Answered By : David Richerby

This answer is based on what I thought an earlier version of the question meant.

It's the hypothesis of a theorem: if $L$ and its complement are R.E., then $L$ is recursive. At least, that is the theorem one would expect to see. In fact, the theorem seems to be "If $L$ and its complement are R.E., then $L$ is R.E.", which is vacuously true.

And, yes, there are plenty of languages $L\in\mathrm{RE}$ for which the complement of $L$ is not in $\mathrm{RE}$.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/29148

3200 people like this

 Download Related Notes/Documents


Post a Comment

Let us know your responses and feedback