MadeEasy Test Series: Theory Of Computation - Decidability

Question

Among II and III. Which one is decidable ? Please explain in detail.

Comments

2. Decidable

3. Undecidable

Answer 1

1. Decidable, membership problem for all language except RE is decidable

2. Decidable, run TM on all strings of length atmost k for k steps and accept if TM accepts at least one of the strings.

3. Undecidable, can be reduced to state entry problem.