0 votes 0 votes IF P1 IS REDUCIBLE TO P2 AND P1 IS RECURSIVE ENUMERABLE THEN P2 NEED NOT BE RECURSIVE ENUMERABLE ???IS IS TRUE ??WHAT I AM THINKING IS THAT P1 IS UNDECIABLE SO P2 WILL ALSO BE UNDECIABLE HENCE SHOULD BE RECURSIVE ENUMERABLE... eyeamgj asked Aug 17, 2018 eyeamgj 980 views answer comment Share Follow See all 8 Comments See all 8 8 Comments reply Show 5 previous comments Vikas Verma commented Aug 17, 2018 reply Follow Share Yes Deepanshu, you're right. Thanks for pointing out. 0 votes 0 votes eyeamgj commented Aug 17, 2018 reply Follow Share i think this is all about symbol representation ...all is basically depend on actual words of question then whatever be the symbol doesnt mean. 0 votes 0 votes Kalpataru Bose commented Aug 21, 2018 reply Follow Share if P1 is reducible to P2 and P1 is recursively enumerable , then P2 may or may not be recursively enumerable. but say if P1 is non recursively enumerable, then P2 is also non recursively enumerable 0 votes 0 votes Please log in or register to add a comment.
0 votes 0 votes If P1<P2 then 1.if P1 is REL then P2 is also REL 2.If P2 is Recursive then P1 is also Recursive 3 If P2 is not Recursive then P1 is also not Recursive 4 If p1 is not REL then p2 is also not REL 5.If p2 is not Recursive Enumerable then so is p1 Spider1896 answered Aug 17, 2018 Spider1896 comment Share Follow See all 8 Comments See all 8 8 Comments reply Show 5 previous comments Spider1896 commented Aug 17, 2018 reply Follow Share The set of halting turing machines is recursively enumerable but not recursive. Indeed one can run the Turing Machine and accept if the machine halts, hence it is recursively enumerable. On the other hand the problem is undecidable.One can understand that the problem of Recursive Enumerable are Semi-decidable or partially decidable but then we consider Partially decidable language as a class of Undecidable Language. Remember state entry problem. That is undecidable moreover it is partially decidable 0 votes 0 votes Bhagyashree Mukherje commented Aug 17, 2018 reply Follow Share I understud this point.but what about problems which are recursive as well as recursive enumerable? Are they also undecidable? 0 votes 0 votes Spider1896 commented Aug 17, 2018 reply Follow Share See actually the concept is that all undecidable problem are need not be REL. Don't get confused into thinking there are three (disjoint) kinds of sets: decidable, semi-decidable, and undecidable. There are two kinds: decidable and undecidable. All of the decidable sets are also semi-decidable (though it's unusual to say it that way). Some of the undecidable sets are also semi-decidable. This is just the same as saying that all enumerable sets are recursively enumerable, and some non-enumerable sets are recursively enumerable. But then consider REL as undecidable because we cannot give any Membership algo too. 0 votes 0 votes Please log in or register to add a comment.