0 votes 0 votes A is Recursively Enumerable but not recursive and A reduces to B then which of the following can be true? A) B is Recursive B) B is Recursive Enumerable C) B is Not RE D) B is CFL Theory of Computation theory-of-computation reduction + – Mk Utkarsh asked Sep 19, 2018 edited Sep 19, 2018 by Mk Utkarsh Mk Utkarsh 491 views answer comment Share Follow See all 8 Comments See all 8 8 Comments reply daksirp commented Sep 19, 2018 reply Follow Share C) B is not RE 0 votes 0 votes Mk Utkarsh commented Sep 19, 2018 reply Follow Share daksirp what's wrong with B? 0 votes 0 votes daksirp commented Sep 19, 2018 reply Follow Share If A ≤m B ==> 'A' cannot be harder than 'B' So in Que : A is RE but Not REC, therefore for 'B' to be hardet than A, only option available is 'NOT RE' if we go with option B : 'B' is RE, it is not possible for 'B' to be harder than 'A', since 'RE' is easy as compared to "RE but not REC" . 0 votes 0 votes srestha commented Sep 19, 2018 reply Follow Share I think A) and B) both true It is ur self doubt right? 0 votes 0 votes Arjun commented Sep 19, 2018 reply Follow Share @daskirp Never do like that. B should be as hard as A meaning it may be r.e. or even non r.e. 1 votes 1 votes daksirp commented Sep 19, 2018 reply Follow Share @Arjun : sir then, is it " 'B' can be as hard as A or 'B' can be harder than 'A' . ? if it is then, 'B' can be "RE but Not REC" too, or 'B' can be 'NOT RE' . but how 'B' can be RE ?. as if we consider 'B' as 'RE', then there exists a subset of 'REC' in RE. where am i going wrong ? 0 votes 0 votes Mk Utkarsh commented Sep 19, 2018 reply Follow Share both B and C are correct. 1 votes 1 votes daksirp commented Sep 19, 2018 reply Follow Share @utkarsh, did u get my point. Why B is correct ? See my response to Arjun sir 0 votes 0 votes Please log in or register to add a comment.