Let \(X\) be a recursive language and \(Y\) be a recursively enumerable but…
2016
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 \(\overline Y\) reduces to \(W\), and \(Z\) reduces to \(\overline 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.
Attempted by 54 students.
Show answer & explanation
Correct answer: C
Key insights: many-one reductions preserve membership in the following sense: if A many-one reduces to B and B is r.e. then A is r.e.; if A many-one reduces to B and B is recursive then A is recursive.
Analyze W: overline Y reduces to W. Since Y is r.e. but not recursive, overline Y is not r.e. If W were r.e., then overline Y would be r.e. via the reduction, a contradiction. Therefore W is not recursively enumerable (and in particular not recursive).
Analyze Z: Z reduces to overline X. X is recursive, so overline X is also recursive. Any language that many-one reduces to a recursive language is recursive (compute the reduction and then decide membership in the recursive target). Hence Z is recursive.
Conclusion: W is not recursively enumerable and Z is recursive.
A video solution is available for this question — log in and enroll to watch it.