GO Classes Test Series 2023 | Theory of Computation | Test 5 | Question: 4

Answer 1

$\text{L1}$ is decidable because This is the empty set, since every language has an infinite number of $\text{TMs}$ that accept it.
$\text{L2}$ is decidable. In this question, we are talking about all the descriptions of Turing machines using a fixed alphabet (of finite size, of course), i.e., $\text{TM’s}$ that are encoded as input to the universal $\text{TM}.$ So, $\text{L2}$ is finite, and hence recursive.

$\textbf{Learn it here :}$
Watch the following lectures for understanding Decidability and Countability, and make sure your at least $2-3$ marks in GATE exam :
https://youtube.com/playlist?list=PLIPZ2_p3RNHiMGiPFIOPJG_ApL43JkILI

Comments

@Pranavpurkar @sk91

$\mathrm{L} 3:=\{\langle \text{M}\rangle \mid \text{M}$ is a $\text{TM},$ and $\text{M}$ is the only $\text{TM}$ that accepts $\mathrm{bab}\mathrm{}\}.$

$L3$ is still Trivially Decidable, because $M$ can never be the “only" TM to accept $bab.$

---

@Deepak Poonia Sir,

so “only” is the keyword here, if it is removed then definitely it is undecidable. right?

---

@Pranavpurkar Yes.