The Gateway to Computer Science Excellence
0 votes


in Theory of Computation by Loyal (5.9k points) | 100 views
option C

3 Answers

+5 votes
Best answer

$X$ is recursive $\implies \bar X$ is also recursive.

$Y$ is r.e. but not recursive $\implies \bar Y$ is not even r.e.

$\bar X$ reduces to $W \implies $ $W$ is recursive or a super set of it.

$\bar Y$ reduces to $Z \implies $ $Z$ is not even r.e.

Correct Answer: C. 

by Veteran (434k points)
selected by
0 votes
Compliment(REC)=REC                                                 X=REC

Compliment (RE but recursive) = RE                                

Compliment (RE but not recursive) = Not RE                     Y=RE but not REC

i.e W=Compliment(X)=REC

    Z=Compliment(Y)=Not RE

D) is correct
by Active (1.3k points) 1 flag:
✌ Spam (Hira Thakur)
0 votes
x complement recursive and y complement not RE hence option D
by (257 points) 1 flag:
✌ Spam (Hira Thakur)
Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true
50,833 questions
57,709 answers
107,602 users