retagged by
657 views
0 votes
0 votes
closed with the note: https://gateoverflow.in/1972/gate2014-2_16

Let L ≤ ML′ denote that language L is mapping reducible (many to one reducible) to language L′. Which one of the following is True?

  1. If L ≤PL′ and L′ is semidecidable then L is semidecidable.
  2. If L ≤ PL′ and L is RE then L′ is RE.
  3. If L ≤ PL′ and L is decidable then L′ decidable.
  4. If L ≤ PL′ and L is recursive then L′ is recursive.

Could anyone please solve this and explain the this reducibility logic ?

retagged by

Related questions

3 votes
3 votes
2 answers
2
im.raj asked Jun 16, 2016
20,842 views
A. [(00(0+1)* 11] + [11( 0 + 1)* 00]B. [(00+11) (0+1)+] + [( 0 + 1)+ (00+11)].C. [(00+11) (0+1)*] + [( 0 + 1)* (00+11)]D. (00+11) (0+1)* (00+11).
0 votes
0 votes
2 answers
4
dhruba asked Jun 5, 2023
1,151 views
Binary search is performed on a sorted array of n elements. The search key is not in the array and falls between the elements at positions m and m+1 (where 1 ≤ m < n). ...