1
$\begingroup$

I know that a recursively enumerable language minus a recursive language results in a recursively enumerable language, but I'm confused with the above question.

Aren't all recursive languages also recursively enumerable? Does this mean the answer to the question is that a recursive language minus a recursively enumerable language results in a recursively enumerable language, but more specifically, a recursive language?

$\endgroup$
1
  • 1
    $\begingroup$ You talk about "the answer to the question" but you don't pose a question: just the statement "A recursive language minus an R.E. language results in a recursive language." It's certainly true that a recursive language (e.g., $\emptyset$) minus an R.E. language (well, any language) is recursive. Is the statement supposed to be that every recursive language minus every R.E. language is recursive? Are you supposed to be proving it? Proving it or finding a counterexample? $\endgroup$ Apr 5, 2016 at 23:37

1 Answer 1

3
$\begingroup$

Let $L$ be an r.e. language which is not recursive (for example, $L$ can be the language of descriptions of Turing machines that halt on the empty input). Then $\Sigma^*$ is recursive but $\Sigma^* \setminus L$ is not recursive (exercise).


More generally, when faced with a question like this, try the following two approaches in parallel:

  1. Try to prove the claim.
  2. Try to refute the claim using a counterexample.

The two approaches can even feed each other.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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