3 votes 3 votes If L1 is reducible to L2 and L1 is recursively enumerable then what can we say about L2? Theory of Computation theory-of-computation + – vaishali jhalani asked Nov 21, 2016 vaishali jhalani 798 views answer comment Share Follow See all 0 reply Please log in or register to add a comment.
Best answer 2 votes 2 votes Given that L1 $\leqslant$ L2 (L1 Reduciable L2) It means L2 is atleast harder problem as L1. And Here Given that L1 is Recursive Enumerable. So, L2 Must be either Recursive Enumerable Language or Non-Recursive Enumerable Language. Rajesh Pradhan answered Nov 21, 2016 • selected Jan 11, 2017 by Rajesh Pradhan Rajesh Pradhan comment Share Follow See all 0 reply Please log in or register to add a comment.
2 votes 2 votes L1 reducible to L2 It refers (L2 is decidable) ==> L1 is decidable Again L1 is Undecidable then L2 is Undecidable(Contrapositive form) Again L2 is REL ==>L1 is REL again L1 is non REL ==> L2 is non REL ShouvikSVK answered Jan 28, 2022 ShouvikSVK comment Share Follow See all 0 reply Please log in or register to add a comment.
0 votes 0 votes we cant say anything about L2. Anusha Motamarri answered Nov 21, 2016 Anusha Motamarri comment Share Follow See all 6 Comments See all 6 6 Comments reply Show 3 previous comments Anusha Motamarri commented Nov 21, 2016 reply Follow Share L2 cant always be recursive. if L1 is reducible to L2. and if L2 is recursive then L1 is recursive which means L1 is recursively ennumerable. this is a case when L2 can be recursive when L1 is recursively ennumerable. but we cant say that L2 can be always recursive 2 votes 2 votes vaishali jhalani commented Nov 21, 2016 reply Follow Share So if L1 is recursively enumerable but not recursive then L2 wii be RE only. 0 votes 0 votes Anusha Motamarri commented Nov 21, 2016 reply Follow Share i think some times L2 may not even be RE too. bcoz L1 reducible to L2 , L1 is RE, it means L2 cant be easier than RE. so it can be RE or not even RE 1 votes 1 votes Please log in or register to add a comment.