GATE CS 2021 (Forenoon) — Question 49

Theory of Computation (TOC)Turing Machines & UndecidabilityMCQ2 marks · −2/3 if wrongMedium

For a Turing machine \(M\), \(\langle M \rangle\) denotes an encoding of \(M\). Consider the following two languages: \(L_1 = \{\langle M \rangle \mid M \text{ takes more than 2021 steps on all inputs}\}\) \(L_2 = \{\langle M \rangle \mid M \text{ takes more than 2021 steps on some input}\}\) Which one of the following options is correct?
  1. A
    Both \(L_1\) and \(L_2\) are decidable.
  2. B
    \(L_1\) is decidable and \(L_2\) is undecidable.
  3. C
    \(L_1\) is undecidable and \(L_2\) is decidable.
  4. D
    Both \(L_1\) and \(L_2\) are undecidable.
Practise the full 2021-FN paper
Challenge a friend: WhatsApp Telegram
Recommended book · affiliate linkIntroduction to Automata Theory (Hopcroft & Ullman)Regular languages, CFGs, pushdown automata and Turing machines.
Practise more on Turing Machines & UndecidabilityTimed, in the real exam interface · free to start

A GATE question every morning

One real past-paper question every morning for your branch, answer hidden until you tap. Free on Telegram.

Join
Stuck? Ask in the student group