Reduction

Question

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

Comments

C) B is not RE

---

daksirp what's wrong with B?

---

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" .

---

I think A) and B) both true

It is ur self doubt

right?

---

@daskirp Never do like that. B should be as hard as A meaning it may be r.e. or even non r.e.

---

@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 ?

---

both B and C are correct.

---

@utkarsh, did u get my point. Why B is correct ? See my response to Arjun sir