980 views
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...

1 Answer

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

Related questions

1 votes
1 votes
0 answers
1
srestha asked Feb 28, 2019
486 views
If $L_{1}\preceq L_{2}$ and $L_{2}$ turing recognizableThen $L_{1}$ cannot beA)not RELB)Context SensitiveC)Context Free​​​​​​​​​​​​​​D)Recursi...
0 votes
0 votes
0 answers
2
Mk Utkarsh asked Sep 19, 2018
492 views
A is Recursively Enumerable but not recursive and A reduces to B then which of the following can be true?A) B is RecursiveB) B is Recursive EnumerableC) B is Not RED) B i...
5 votes
5 votes
1 answer
3
junaid ahmad asked Sep 26, 2017
611 views
please give proper reasoning.