6
$\begingroup$

I am having a hard time understanding closure properties of recrusively enumerable languages. I have read the explanation on this site but still unable to fully understand why they are not closed under complementation?

Explanation also says,

This fails because $M$ only needs to halt if $w \in L(M)$ - doesn't have to say "no".

What does it mean?

Improve this question
$\endgroup$
2
  • $\begingroup$ I know that a language is RECURSIVE if TM accepts or rejects and halts in either case and RE(recursively enumerable) if TM either accepts and halts or loops forever. $\endgroup$
    – c2h5oh
    Commented Feb 4, 2014 at 11:26
  • 1
    $\begingroup$ Please don't scream... $\endgroup$
    – Raphael
    Commented Feb 4, 2014 at 11:38

2 Answers 2

Reset to default
6
$\begingroup$

The statement you quote is an argument why the proof for showing that $\mathrm{R}$ (the set of recursive languages) is closed against complement does not work for $\mathrm{RE}$ (the set of recursively enumerable languages). It's not a proof of the reverse in itself -- another proof may still work!

The problem is that flipping the result of a TM only works if you get a result; $\mathrm{RE}$ promises only an acceptor, not a decider, which may loop if the input is not in the language. Therefore, you can not flip properly; all you'd get is a machine that says "no" of the word is not the language but loops otherwise. That's a machine for $\mathrm{co\text{-}RE}$, not $\mathrm{RE}$.

As for why $\mathrm{RE}$ is not closed against complement, the site you link contains all the answers; let me reiterate.

  1. If $L$ and $\overline{L}$ are both semi-decidable, then both are decidable.
  2. Hence, if $\mathrm{RE}$ was closed against complement, we'd have $\mathrm{R} = \mathrm{RE}$.
  3. But we know that $\mathrm{R} \subsetneq \mathrm{RE}$ (by witness of the halting problem), so this can't be true.
Improve this answer
$\endgroup$
4
  • $\begingroup$ what do you mean by "you can not flip properly" ? $\endgroup$
    – c2h5oh
    Commented Feb 4, 2014 at 12:04
  • 2
    $\begingroup$ @c2h5oh You can flip the result of a TM, i.e. make it say “accept” instead of “reject” and “reject” instead of “accept”. But if the original TM does not terminate on some input, the flipped TM also does not terminate on that input. So the flipping does not produce a machine that recognizes the complement of the language. $\endgroup$
    – Gilles 'SO- stop being evil'
    Commented Feb 4, 2014 at 12:09
  • $\begingroup$ This is how I proved union property for RE Union: For any two RE language L1 and L2, let M1 and M2 be the TMs that recognize them. We construct a TM M that recognizes the union of L1 and L2. - For the input w - Run M1 and M2 in parallel. - If either accept, accept - If both reject, reject. If M1 and M2 accept w, M accepts w in a finite number of steps. If M1 and M2 reject by looping, M also loops. can't we do similar thing for complementation ? i.e. TM for complement of L will say "reject" if the string is in L and loops forever and accepts and prints "accept" $\endgroup$
    – c2h5oh
    Commented Feb 4, 2014 at 12:11
  • 1
    $\begingroup$ @c2h5oh the problem in your argument is in the "loops forever and accept". If you loop forever, you can't accept, because you never finish looping. Looping forever is always an implicit reject of the input. In other words there is no way to print "accept" after an infinite looping. $\endgroup$
    – Denis
    Commented Feb 4, 2014 at 16:58
0
$\begingroup$

The class of recursively enumerable languages is not closed under complementation, because there are examples of recursively enumerable languages whose complement is not recursively enumerable. Those examples come from languages that are recursively enumerable, but not recursive.

One of those examples is the language $L=\{(M, w) : M\ \text{is a Turing Machine and}\ w \in L(M)\}$. This language is recognizable (and hence recursively enumerable), because you can always run Turing Machine $M$ with input $w$, and if $w \in L(M)$, $M$ will halt accepting $w$. It has been shown that this language ($L$) is not decidable.

Now, suppose that $\overline{L}$ (complement of $L$) were also recognizable, then $L$ becomes decidable, because we could use the recognizers for $L$ and for $\overline{L}$ to build a decider for $L$. But since we already now that $L$ is not decidable, then, $\overline{L}$ cannot be recognizable, and hence, the class of recursively enumerable languages is not closed under complementation.

Improve this answer
$\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.