edited by
1,582 views
2 votes
2 votes
If P1<=P2 means P1 is reducible to p2,then which is true?

1, If P1 is RE But Not REC,P2 is also RE but not REC?

2. If P2 is RE But Not REC,P1 is also RE but not REC?

As per my understanding ,if P1 is undecidable then P2 is undecidable,so If i consider RE BUT NOT REC as undecidable,then answer will be 1 is true

Also i know if P2 is RE then P1 is also RE is correct,As per this result,RE BUT NOT REC is also RE,so 2 is true.

Please help

Edit:- As a part of this solution please tell me,whether undecidable includes semidecidable also?And whether semidecidable includes decidable also?
edited by

1 Answer

2 votes
2 votes

Decidable means RECURSIVE and undecidable means either Turing Recognizable(aka RE/semi decidable) or Totally Undecidable(NOT RE).

If P1 is reduciable to P2     (P1-->P2)

then if P1 is decidable then P2 may be decidable or undecidable.

If P1 is undecidable then P2 is also Undecidable

If P2 is Undecidable then P1 may be decidable or undecidable.

If P2 is Decidable then P1 will be definitly Decidable.

If P2 is RE then so is P1.

If P2 is REC then P1 hen 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...
1 votes
1 votes
0 answers
3
Sumaiya23 asked Jan 23, 2018
428 views
What is monotonic and non-monotonic property. Please explain the second postulate of Rice's Theorem.