## Recursive-Enumerable-Languages

Question 1 |

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 reduces to W, and Z reduces to (reduction means the standard many-one reduction). Which one of the following statements is **TRUE**?

W can be recursively enumerable and Z is recursive. | |

W can be recursive and Z is recursively enumerable. | |

W is not recursively enumerable and Z is recursive. | |

W is not recursively enumerable and Z is not recursive. |

Question 1 Explanation:

The rules are:

If A ≤

Rule 1: If B is recursive then A is recursive

Rule 2: If B is recursively enumerable then A is recursively enumerable

Rule 3: If A is not recursively enumerable then B is not recursively enumerable

Since X is recursive and recursive language is closed under compliment, so is also recursive.

: By rule 3, W is not recursively enumerable.

: By rule 1, Z is recursive.

Hence, W is not recursively enumerable and Z is recursive.

If A ≤

_{p}BRule 1: If B is recursive then A is recursive

Rule 2: If B is recursively enumerable then A is recursively enumerable

Rule 3: If A is not recursively enumerable then B is not recursively enumerable

Since X is recursive and recursive language is closed under compliment, so is also recursive.

: By rule 3, W is not recursively enumerable.

: By rule 1, Z is recursive.

Hence, W is not recursively enumerable and Z is recursive.

There is 1 question to complete.