# $L \in RE$ Question [closed]

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

• I don't get it, either. Is the question: "If L is RE but the complement of L is not RE, can we build a TM that halts on all words in L?" – Raphael Aug 15 '14 at 9:15
• Now the question makes no sense. The yellow box used to contain something that was a quote, paraphrase or translation from an exam paper. Now it contains the asker's question. Please, @user3661613, write a clear question once and for all. My answer, which you accepted, no longer makes any sense because you've changed the question. – David Richerby Aug 15 '14 at 9:15
• The use of present tense together with removing the phrasing of the problem leaves a bad after-taste. Are you currently taking the exam? – Raphael Aug 15 '14 at 9:25

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}$.
• I don't understand your question but you seem to be confused about the basic definitions. If $L$ is recursive, there is a Turing machine that halts for all inputs, accepts every word in $L$ and rejects every word not in $L$. If $L$ is RE, there is a Turing machine that halts for all inputs in $L$ and does not halt for any input not in $L$. The theorem in the original question is "If $L$ and its complement are RE then $L$ is recursive." – David Richerby Aug 15 '14 at 9:03