Let X be a recursive language and Y be a recursively enumerable but not recursive language. Let W and Z be two languages such that Y’ reduces to W, and Z reduces to X’ (reduction means the standard many-one reduction). Which one of the following statements is TRUE?
A. W can be recursively enumerable and Z is recursive.
B. W can be recursive and Z is recursively enumerable.
C. W is not recursively enumerable and Z is recursive.
D. W is not recursively enumerable and Z is not recursive
Answer:C
Let X be a recursive language and Y be a recursively enumerable but not recursive language. Let W and Z be two languages such that Y’ reduces to W, and Z reduces to X’ (reduction means the standard many-one reduction). Which one of the following statements is TRUE?
A. W can be recursively enumerable and Z is recursive. B. W can be recursive and Z is recursively enumerable. C. W is not recursively enumerable and Z is recursive. D. W is not recursively enumerable and Z is not recursive