-3
$\begingroup$

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

|cite|improve this question
$\endgroup$

closed as unclear what you're asking by Raphael♦ Aug 15 '14 at 9:26

Please clarify your specific problem or add additional details to highlight exactly what you need. As it's currently written, it’s hard to tell exactly what you're asking. See the How to Ask page for help clarifying this question. If this question can be reworded to fit the rules in the help center, please edit the question.

  • $\begingroup$ 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?" $\endgroup$ – Raphael♦ Aug 15 '14 at 9:15
  • $\begingroup$ 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. $\endgroup$ – David Richerby Aug 15 '14 at 9:15
  • $\begingroup$ The use of present tense together with removing the phrasing of the problem leaves a bad after-taste. Are you currently taking the exam? $\endgroup$ – Raphael♦ Aug 15 '14 at 9:25
1
$\begingroup$

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

|cite|improve this answer
$\endgroup$
  • $\begingroup$ you means and as a direct result of L is recursive then there is a TM that halt on all words in L ? $\endgroup$ – user3661613 Aug 15 '14 at 9:01
  • 1
    $\begingroup$ 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." $\endgroup$ – David Richerby Aug 15 '14 at 9:03

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