# Non Turing-Recognizable from symmetric difference

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?

• 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

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).