5
$\begingroup$

I'm studying Turing Machines and I've already showed how Turing-Decidable is closed for the operations of Union, Intersection, Concatenation, Complement and Kleene Star. Next I did some demonstrations to show how T-Recognizable languages are closed for Union, Intersection, Concatenation and Kleene Star.

Now I'm trying to answer a question to show why the classe of T-Recognizable languages are not closed for the operation of Complementation, but I cannot understand it. Could someone please explain this?

$\endgroup$
  • 4
    $\begingroup$ First of all, what standard textbooks on this topic have you looked at? Every one of them is going to have a proof. $\endgroup$ – Andrej Bauer Apr 7 '13 at 17:53
9
$\begingroup$

Hint: Suppose it was. Let $L$ be a recognizable language and let $\overline{L}$ be its complement. If $\overline{L}$ was recognizable as well, let $M_1$ and $M_2$ be recognizers of $L$ and $\overline{L}$, respectively.

Can you now use $M_1$ and $M_2$ to construct a decider for $L$? What does this mean for undecidable and recognizable problems like the halting problem?

$\endgroup$
4
$\begingroup$

Intuitively, a TM $M$ can recognize $L$ if you run it on $\sigma \in L$ it will eventually halt and say "Yes"; there is no way of knowing if when run on $\sigma' \not\in L$ it will ever halt.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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