Discussion
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?
Answer: C
The true statement is \(W\) is not recursively enumerable and \(Z\) is recursive.
\(Y\) is recursively enumerable but not recursive, so its complement \(\overline{Y}\) is not recursively enumerable (if both a language and its complement were RE, the language would be recursive). \(\overline{Y}\) reduces to \(W\), and a reduction transfers recursive enumerability downward: if \(W\) were RE, \(\overline{Y}\) would be RE too. So \(W\) is not RE.
\(X\) is recursive, so \(\overline{X}\) is recursive as well. \(Z\) reduces to \(\overline{X}\), so a decider for \(\overline{X}\) combined with the reduction decides \(Z\): \(Z\) is recursive.
The options saying \(W\) can be RE or recursive contradict the first argument, and the one saying \(Z\) is not recursive contradicts the second. Note the bars: the reductions are from \(\overline{Y}\) and to \(\overline{X}\).
Post your comment
Please log in or register to post a comment.
Examination Categories
- SSC Exams
- Banking Exams
- Teaching Exams
- Civil Services Exams
- Railways Exams
- Engineering Recruitment Exams
- Defence Exams
- State Government Exams
- Police Exams
- Insurance Exams
- Nursing Exams
- Other Government Exams
- NRA CET
- PG Entrance Exams
- Campus Placement
- MBA Entrance Exams
- CUET and UG Entrance
- Judiciary Exams
- Regulatory Body Exams
- Software Development