2
$\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).

Improve this question
$\endgroup$
  • $\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
4
$\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}$.

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.