Virtual Gate Test Series: Theory Of Computation - Decidable Language

Question

$L$ is surely decidable if 

(A) both $L$ and its complement are not recognizable 

(B) $L \subseteq \{0\}^*$

(C) $L \leq_m \{0^n1^n\;\mid\;n\geq0\}$

(D) $L^R$ is decidable

Answer 1

both  C and D are true , If LR is decidable then we can easily construct a turing machine which reverses the input and feeds it to turing machine for LR  to get turing machine for L, so L is also decidable . Similarly if L is reducible to L1 = 0n 1n then as L1 is decidable so L is also decidable.

Comments

WHAT IS THE PROBLEM IN option b

---

Every Language is a subset of {0}* so even undecidable languages are subsets of it so we cannot say for sure that at  L which is a subset of {0}* is decidable.

---

WHat about option C?

---

i think option c and d are decidable instead of b option

---

how can u say that every language is subset of {0*}

---

D always correct??i.e Lr decidable>L decidable??

---

Does not decidability concept goes backward