Theory of Computation Recursively Enumerable Sets, Turing Machines and Undecidability Undecidability
Let A be a recursively enumerable language which is not recursive and A’ be its complement, also B be recursive language and B’ be its complement. Let X and Y be two languages such that A’ reduces to X and Y reduces to B’ and the reduction is many to one. Which of the following is/are true?
1
X can be recursively enumerable language
2
X is not recursively enumerable language
3
Y is recursive language
4
Y may or may not be recursive language