1
$\begingroup$

If A and B are Turing recognizable, is A - B Turing recognizable?

I think that A - B would be Turing recognizable because they're both in the space of Turing recognizability. For example, if A is context free and B is a regular language A - B would result in a language that is sill Turing recognizable.

However, does this become a question about emptiness? Two Turing recognizable languages equal to each other leave an empty set. Is the empty set Turing recognizable? I would still say yes.

Not sure if I'm thinking about this correctly...

$\endgroup$
  • 2
    $\begingroup$ Hint: what is another way of writing $A-B$? $\endgroup$ – Ryan Jun 8 '15 at 22:35
  • 2
    $\begingroup$ ... or when $A=\Sigma^*$? $\endgroup$ – Ran G. Jun 8 '15 at 22:37
  • 1
    $\begingroup$ Also, consider the asymmetry of the definition of Turing recognizability (i.e., that a recognizer says "yes" in a rather different way to how it says "no"). $\endgroup$ – David Richerby Jun 8 '15 at 22:57
  • $\begingroup$ Please, Alan Turing is a great scientist, and even if he were not, he would still be entitled to a name starting with a capital letter. He deserves it considerabl;y more than Mr Context Free. $\endgroup$ – babou Jun 8 '15 at 22:57
  • 1
    $\begingroup$ Unfortunately, no. $A\setminus B$ is indeed a subset of $A$, a recognizable language, but generally a subset of a language with a certain property will not have that property. For an extremely simple example, let $B$ be a finite language and $A=\Sigma^*$. Then $A\setminus B$ is certainly not finite. $\endgroup$ – Rick Decker Jun 9 '15 at 0:00
5
$\begingroup$

Suppose that $L$ is a Turing-recognizable language and $L^C$ is its complement. Let's assume, for the purposes proof by contradiction, that $L^C$ is also Turing-recognizable. This means that a recognizer exists for each of these two languages: we will call them $M_L$ and $M_{L^C}$. How might we use these two recognizers to do something absurd?

For starters, we can construct a decider for the language $L$. Given any string $w$, we can use it as input for both $M_L$ and $M_{L^C}$. $M_L$ will halt and accept if $w$ is in $L$ (and halt and reject or loop forever if not). Conversely, $M_{L^C}$ will halt and accept if $w$ is in $L^C$ (and halt and reject or loop forever otherwise). In any case, our constructed machine will halt with a decision about $w$, and so we've proven the existence of a decider for $L$.

By assuming that any Turing-recognizable language $L$ is closed under complement, we can show that $L$ is also Turing-decidable, which implies that $R=RE$. So we must conclude that Turing-recognizable languages are not closed under complement!

If they're not closed under complement, is it possible for them to be closed under set difference? (Hint: the set of Turing-recognizable languages is closed under intersection. Can you rewrite $A-B$ in terms of complement and intersection?)

(Solution: $A-B$ can be written $A \cap B^C$; loosely speaking, both describe the set of elements which belong to $A$ but not to $B$. Since set difference can be expressed using intersection and complement operators, and since Turing-recognizable languages are not closed under complement, we conclude that Turing-recognizable languages are not closed under set difference.)

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ A intersect B is equal to (A complement union B complement) complement $\endgroup$ – Yawn Jun 9 '15 at 1:06
  • $\begingroup$ Maybe A - B is equal to A intersect B complement $\endgroup$ – Yawn Jun 9 '15 at 1:11
  • $\begingroup$ That's right. $A - B$ is 'the set of elements which are in $A$ except for those in $B$.' Since $A \cap B$ is 'the set of elements in both $A$ and $B$' and $B^C$ is 'the set of elements which are not in $B$,' then $A \cap B^C$ is 'the set of elements which are in $A$ and not in $B$.' Which is $A - B$! $\endgroup$ – Qalnut Jun 9 '15 at 1:38

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.