Take the 2-minute tour ×
Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It's 100% free, no registration required.

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|improve this question
Hint: one of the languages consists of all strings. –  Yuval Filmus Feb 14 '13 at 5:59
What have you tried? –  Raphael Feb 14 '13 at 6:35
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
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
show 3 more comments

Your Answer


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

Browse other questions tagged or ask your own question.