Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

I have a question about how you would find a example of a non Turing-recognizable language from the symmetric difference of two Turing-recognizable languages. I believe this is possible, but I am having problems coming up with a example in my head. Does anyone have any hints, or ideas about how to think about this?

share|cite|improve this question
Hint: one of the languages consists of all strings. – Yuval Filmus Feb 14 '13 at 5:59
I was thinking of it in terms of sets, so the Turing-recognizable set is a subset of non Turing-recognizable. But if this is the case, then no symmetric difference could contain a non Turing-recognizable language. The only cases I could think of is if you take cases like if the symmetric difference was the empty set... – trev9065 Feb 14 '13 at 16:53
Another hint: A language is Turing-recognizable but not Turing-decidable if... – Yuval Filmus Feb 14 '13 at 17:28
@YuvalFilmus A language is Turing-recognizable but not Turing-decidable if it loops on some inputs and neither accepts or rejects, right? – trev9065 Feb 14 '13 at 20:23
A language doesn't "loop". A Turing machine could loop on a specific instance. A language is Turing-decidable is there is a Turing machine that always stops and answers YES or NO correctly. It is Turing-recognizable if there exists a Turing machine that either outputs YES or never terminates (there are other, equivalent definitions). – Yuval Filmus Feb 14 '13 at 22:14

(Converting the comment hints and guidance into an answer)

If you take $A$ to consist of all strings, $A=\Sigma^*$, then $A$ is decidable and recognizable. Then, we will take the second language, $B$, to be recognizable but not decidable.

Their symmetric difference will give us (by definition) $\overline B \triangleq \Sigma^* \setminus B$.

Now, let's get concrete. The halting problem, $HP$, is a recognizable non-decidable language. If we take $A=\Sigma^*$ and $B=HP$, then their symmetric difference is $\overline {HP}$. The last step is to show that $\overline {HP}$ is not-recognizable (but this is a very well known fact that $\overline{HP}\in coRE$ and not-recognizable, since if it was recognizable, then $HP$ would have become decidable, since for any input we would have a machine that says "yes" if it is the language, and another machine that says "no" if it is not).

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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