engineering recuitment GATE CSE 2023-24 Test Series Theory of Computation Recursively Enumerable Sets, Turing Machines and Undecidability Undecidability
Let L1 ≤m L2 denote the language L1 is mapping reducible (many to one reducible) to language L2. Which of the following options is/are correct(s)?
1
If L2 is decidable then L1 is decidable.
2
If L1 is undecidable then L2 is undecidable.
3
If L2 is semi–decidable then L1 is semi–decidable.
4
If L2 is undecidable then L1 is undecidable.