patternModerate
Why isn't the class of Turing-Recognizable languages closed under Complement?
Viewed 0 times
whythelanguagesclosedrecognizableundercomplementturingisnclass
Problem
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?
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?
Solution
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?
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?
Context
StackExchange Computer Science Q#11104, answer score: 12
Revisions (0)
No revisions yet.