Consider the following languages. aligned L1 &= \ M M takes at least 2016 steps on some input\, L2 &= \ M M takes at least 2016 steps on all inputs\ and L3 &= \ M M accepts \, aligned where for each Turing machine M, M denotes a specific encoding of M. Which one of the following is TRUE? A) L1 is recursive and L2, L3 are not recursive B) L2 is recursive and L1, L3 are not recursive C) L1, L2 are recursive and L3 is not recursive D) L1, L2, L3 are recursive

Official answer: C) L1, L2 are recursive and L3 is not recursive. Explanation: To determine the decidability (recursiveness) of each language: 1. Language L1: In 2016 steps, a Turing Machine M can scan at most the first 2016 cells of its tape. Therefore, its behavior within the first 2016 steps depends exclusively on the prefix of the input string of length at most 2016. Over a finite input alphabet , the set of all possible input strings of length at most 2016 is finite. A decider can simulate M on each of these finitely many input strings for up to 2016 steps. If M takes at least 2016 steps on at least one such input, accept; otherwise, reject. Since the simulation is guaranteed to terminate in finite time, L1 is recursive. 2. Language L2: Using the exact same reasoning, if M takes at least 2016 steps on all inputs of length at most 2016, it will take at least 2016 steps on every possible input (since longer inputs cannot affect the first 2016 steps). A decider can simulate M on all inputs of length 2016 up to 2016 steps. If M executes at least 2016 steps on every one of them, accept; otherwise, reject. Thus, L2 is recursive. 3. Language L3: L3 is the empty string (or blank tape) acceptance problem for Turing machines. By Rice's Theorem (or via standard reduction from the Halting Problem HTM), deciding whether a Turing machine accepts the empty string is undecidable. Thus, L3 is not recursive. Therefore, L1, L2 are recursive and L3 is not recursive, matching option (C).

A) L1 is recursive and L2, L3 are not recursive

B) L2 is recursive and L1, L3 are not recursive

C) L1, L2 are recursive and L3 is not recursive

Theory of Computation · Turing Machines and Undecidability

Official IIT answer key · IISc Bangalore · Audited Aug 2026

Take topic test

GATE CSE 2016 Set 2 Q44 · MCQ · 2 marks

Consider the following languages. $\begin{aligned} L_1 &= \{\langle M \rangle \mid M \text{ takes at least 2016 steps on some input}\}, L_2 &= \{\langle M \rangle \mid M \text{ takes at least 2016 steps on all inputs}\} \text{ and} L_3 &= \{\langle M \rangle \mid M \text{ accepts } \varepsilon\}, \end{aligned}$ where for each Turing machine $M$ , $\langle M \rangle$ denotes a specific encoding of $M$ . Which one of the following is TRUE?

Select an option to check

Key concept

Turing Machines and Undecidability

Step-by-step verified solution

Examiner trap & misconception

Topic notes

How GATE tests Turing Machines and Undecidability

Across GATE CS, 'Turing machines and undecidability' is consistently tested through theoretical properties of computability and complexity classes. Questions primarily assess language hierarchies (Recursive vs. Recursively Enumerable), closure properties under complement and set operations, mapping reductions (A m B), and Rice's Theorem applied to TM behavior. A frequent focus is distinguishing semantic properties of languages (undecidable) from finite-step or prefix-bounded properties of machine computations (decidable).

Full Turing Machines and Undecidability guide →

More on Turing Machines and Undecidability

All 30 questions on Turing Machines and Undecidability →

Independent practice explanation verified by the GateAI team. GATE is conducted by the IITs; question text follows the official paper.

Theory of Computation · Turing Machines and Undecidability

Official IIT answer key · IISc Bangalore · Audited Aug 2026

Take topic test

GATE CSE 2016 Set 2 Q44 · MCQ · 2 marks

Consider the following languages. $\begin{aligned} L_1 &= \{\langle M \rangle \mid M \text{ takes at least 2016 steps on some input}\}, L_2 &= \{\langle M \rangle \mid M \text{ takes at least 2016 steps on all inputs}\} \text{ and} L_3 &= \{\langle M \rangle \mid M \text{ accepts } \varepsilon\}, \end{aligned}$ where for each Turing machine $M$ , $\langle M \rangle$ denotes a specific encoding of $M$ . Which one of the following is TRUE?

Select an option to check

Key concept

Turing Machines and Undecidability

Step-by-step verified solution

Examiner trap & misconception

Topic notes

How GATE tests Turing Machines and Undecidability

Full Turing Machines and Undecidability guide →

More on Turing Machines and Undecidability

All 30 questions on Turing Machines and Undecidability →

Independent practice explanation verified by the GateAI team. GATE is conducted by the IITs; question text follows the official paper.

Step-by-step verified solution

Check you can still solve Turing Machines and Undecidability under a clock

More from GATE CSE 2016 Set 2

More on Turing Machines and Undecidability

Step-by-step verified solution

Check you can still solve Turing Machines and Undecidability under a clock

More from GATE CSE 2016 Set 2

More on Turing Machines and Undecidability

Step-by-step verified solution

Check you can still solve Turing Machines and Undecidability under a clock

More from GATE CSE 2016 Set 2

More on Turing Machines and Undecidability

Share this solution

Step-by-step verified solution

Check you can still solve Turing Machines and Undecidability under a clock

More from GATE CSE 2016 Set 2

More on Turing Machines and Undecidability

Share this solution