0
$\begingroup$

I'm learning about Turing Machines, decidability, and recognizability, and read that if a language is recognizable, its complement is sometimes recognizable. I don't really understand how this could be, can someone give me an example where a language has a recognizable complement and an unrecognizable complement? Thank you!

$\endgroup$
1
$\begingroup$

Example 1. The empty language is recognizable and its complement (the language containing all the words) is also recognizable.

Example 2. Any regular language is recognizable and, since regular languages are closed under complement, its complement is also recognizable.

Example 3. The language $H = \{ \langle T, x \rangle : T \mbox{ is a Turing Machine}, x \in \{0,1\}^*, T(x) \mbox{ halts}\}$ is recognizable. In order to recognize $H$ it suffices to build a Turing machine $M$ that checks if $T$ is a valid description of a Turing machine, simulates $T$ on $x$ until $T(x)$ halts (possibly forever), and accepts.

The complement $\overline{H}$ of $H$, however, is not recognizable as if it was recognizable a Turing machine $M'$ for $\overline{H}$, together with $M$, would allow to solve the Halting problem. To do so simply simulate in parallel $M$ and $M'$ until one of them accepts.

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