GO Classes Test Series 2024 | Mock GATE | Test 13 | Question: 55

Answer 1

$\mathrm{A}$ is undecidable but recognizable.

$\text{B}$ is unrecognizable.

$\mathrm{C}$ is undecidable but recognizable.

$\mathrm{D}$ is decidable. There is no input $n$, such that ALL TMs halt on $n.$ So, statement in option D is Trivially Not true, hence, decidable. 

GO Classes Complete Revision, Marathon \& Practice on Decidability, Undecidability, Rice Theorem: https://youtube.com/playlist?list=PLIPZ2_p3RNHiMGiPFIOPJG_ApL43JkILI&feature=shared

After watching the above playlist, you can solve more than $95 \%$ questions on Decidability easily.

Comments

got it sir..

---

@Deepak Poonia Sir option A we can think of monotonic property hence it could be REL or NON REL. so how can we tell it is non REL. Can you please tell me where i am thinking wrong?

---

@Kanha3112, Option A is RE but Not REC.

Option A is RE because if TM $M$ halts on input $0,$ we can verify it in finite amount of time.