What are common examiner traps in Turing Machines and Undecidability?

Assuming Rice's Theorem applies to properties of the machine execution itself (e.g., 'M executes at least 2000 steps') rather than the language L(M) recognized. Reversing the direction of reduction: given A ≤m B, knowing A is decidable/RE tells nothing about B, and knowing B is undecidable/not RE tells nothing about A. Confusing Context-Free Language closure under complementation (CFLs are NOT closed under complement, but the complement of a CFL is always recursive/decidable). Assuming that because a problem is undecidable, it cannot be Recursively Enumerable (forgetting semi-decidability via dovetailed simulation). Confusing L(G) = ∅ (decidable for CFGs) with L(G) = * (undecidable for CFGs). Confusing the set of strings * (countably infinite) with the set of languages 2 * (uncountably infinite). Assuming * is finite because is finite. Assuming 2 * is countable because it is constructed over a finite alphabet . Assuming CFLs are closed under intersection by analogy to regular or recursive languages (e.g. confusing context-free with deterministic context-free or regular). Confusing the intersection of two CFLs with the intersection of a CFL and a regular language (which is context-free).

GATE CSE Turing Machines and Undecidability PYQs

Medium yield24.4% of Theory of Computation

Across GATE CS, 'Turing machines and undecidability' is consistently tested through theoretical properties of computability and complexity classes. Questions pr… Read the guide

Take topic test

Questions: 30
Asked: since 2012
Total marks: 44
Marks / paper: 1.7

30 GATE CSE Turing Machines and Undecidability PYQs with solutions, from Theory of Computation. Browse all GATE CSE PYQs.

Questions

Every official paper that asked this topic, newest first.

What GATE tests in Turing Machines and Undecidability

Concepts, patterns, formulas and traps distilled from past papers.

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 \le_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).

Core concepts

Rice's Theorem (semantic/non-trivial properties of RE languages vs syntactic/step-bounded properties)
Post's Theorem and complementation of RE / REC languages
Many-to-one (mapping) reduction (A ≤m B) and its directional properties
Polynomial-time reduction (A ≤p B) and NP-completeness foundations
Decidability hierarchy: Regular (all standard decision problems decidable), CFL (emptiness, finiteness, membership decidable; universality, equivalence, ambiguity undecidable), TM (almost all semantic problems undecidable)
Deterministic vs. Non-Deterministic Turing Machine equivalence
Countable set of TMs vs. Uncountable set of languages (subset cardinality arguments)
Formal definition of deciders vs recognizers (halting on all inputs)
Countability of * (set of all finite strings)
Uncountability of 2 * (power set of all strings / set of all languages)
Application of Cantor's theorem to formal languages
Lexicographical ordering of finite strings
Closure properties of Regular languages
Closure properties of Context-Free languages (CFLs)
Closure properties of Recursive (Decidable) languages
Closure properties of Recursively Enumerable (Turing-recognizable) languages
Non-closure of CFLs under intersection

Recurring question patterns

Rice's Theorem and Semantic Properties vs. Step-Bounded Behavior
CommonMCQ2 marks2022, 2021, 2020, 2016
Determining whether a language encoding TM properties (e.g., $L = \{\langle M \rangle \mid P(L(M))\}$ ) is decidable or undecidable. Tests understanding that non-trivial semantic properties of $L(M)$ are undecidable by Rice's Theorem, whereas properties bounding the number of execution steps (e.g., 'takes more than $k$ steps') or finite tape head prefixes are decidable by bounded simulation.
Chomsky Hierarchy Decidability and Decision Properties Matrix
CommonMCQ1 marks2025, 2021, 2017, 2016
Evaluating the decidability of classical decision problems (emptiness, universality, membership, equivalence, ambiguity, regularity) across Regular, Context-Free, and Turing-recognizable languages.
Mapping Reductions and Computability Propagation
CommonMCQ2 marks2016, 2015, 2014
Analyzing implications of mapping reducibility ( $A \le_m B$ or $A \le_p B$ ) regarding decidability, recursive enumerability, and complexity classes (P, NP, NP-complete, NP-hard). Focuses on contrapositive arguments and directional inference.
Complement and Post's Theorem Combinations
Commonmixed1 marks2022, 2018, 2016, 2015
Questions evaluating the relationship between a language $L$ and its complement $\overline{L}$ (e.g., $L \in \text{REC} \iff L \in \text{RE} \land \overline{L} \in \text{RE}$ , or unions/intersections of different classes in the hierarchy).
Fundamental Definitions and Cardinality / Set-Theoretic Arguments
Occasionalmixed1 marks2026, 2022, 2021, 2018
Testing core formal definitions of Turing machines (deciding vs. recognizing), countability of Turing machines vs. uncountability of languages, and existence of undecidable subsets within infinite regular languages.
Cardinality and Countability of Strings vs Languages
RareMCQ1 marks2014
Determining whether string universes ( $\Sigma^*$ ) and language sets ( $2^{\Sigma^*}$ ) or specific language classes are countable or uncountable.
Closure Property Evaluation across Chomsky Hierarchy
CommonMSQ1 marks2023
A set of theoretical assertions asking which closure properties hold for different classes of formal languages (Regular, CFL, Recursive, RE) under set-theoretic operations.

Formulas GATE uses

Post's Theorem

L \in \text{REC} \iff (L \in \text{RE}) \land (\overline{L} \in \text{RE})

Used when analyzing the decidability of $L$ given the enumerability of $L$ and $\overline{L}$ .

Mapping Reduction Decidability Transfer

A \le_m B \land B \in \text{REC} \implies A \in \text{REC}

Used when deducing the recursiveness or undecidability of languages under many-one reductions.

Mapping Reduction RE Transfer

A \le_m B \land B \in \text{RE} \implies A \in \text{RE}

Used when determining semi-decidability transfer or its contrapositive ( $A \notin \text{RE} \implies B \notin \text{RE}$ ).

Polynomial Reduction P Transfer

L_1 \le_p L_2 \land L_2 \in \text{P} \implies L_1 \in \text{P}

Used in complexity class questions involving reductions among problems in P, NP, and NP-hard.

Graph of a Computable Function

L_f = \{x\#f(x) \mid x \in \Sigma^*\} \in \text{REC} \iff f \text{ is total computable}

Used when relating functional computability of $f$ to language decidability of its encoding.

Cardinality of String Universe $\Sigma^*$

|\Sigma^*| = \aleph_0

Used to establish that the set of all finite strings over a finite alphabet is countably infinite via standard lexicographical enumeration.

Cantor's Theorem for Language Universe

|2^{\Sigma^*}| = 2^{\aleph_0} = \mathfrak{c} > \aleph_0

Used to prove that the set of all possible languages over $\Sigma$ is uncountably infinite.

De Morgan's Law for Regular Languages

L_1 \cap L_2 = \overline{\overline{L_1} \cup \overline{L_2}}

Proving closure of regular languages under intersection using closure under complementation and union.

Examiner traps in Turing Machines and Undecidability

Assuming Rice's Theorem applies to properties of the machine execution itself (e.g., 'M executes at least 2000 steps') rather than the language L(M) recognized.
Reversing the direction of reduction: given A ≤m B, knowing A is decidable/RE tells nothing about B, and knowing B is undecidable/not RE tells nothing about A.
Confusing Context-Free Language closure under complementation (CFLs are NOT closed under complement, but the complement of a CFL is always recursive/decidable).
Assuming that because a problem is undecidable, it cannot be Recursively Enumerable (forgetting semi-decidability via dovetailed simulation).
Confusing L(G) = ∅ (decidable for CFGs) with L(G) = * (undecidable for CFGs).
Confusing the set of strings * (countably infinite) with the set of languages 2 * (uncountably infinite).
Assuming * is finite because is finite.
Assuming 2 * is countable because it is constructed over a finite alphabet .
Assuming CFLs are closed under intersection by analogy to regular or recursive languages (e.g. confusing context-free with deterministic context-free or regular).
Confusing the intersection of two CFLs with the intersection of a CFL and a regular language (which is context-free).

How questions are asked

Multi-statement true/false evaluation across closure and decidability properties
Classification of TM property languages into decidable, RE but undecidable, or not RE
Identification of decidable vs undecidable problems from a listed set of classical decision questions
Mapping reduction implication checks (A ≤m B / P ≤p Q)
MSQ selection of all true computability assertions
Direct conceptual multiple-choice question on countability properties
Identify correct/incorrect statements regarding closure properties across language classes (MSQ/MCQ).

Paper trends

Introduction of step-bounded TM decision problems (e.g., simulating $M$ for $k$ steps on inputs of bounded length) as a recurring counter-example to Rice's Theorem.
2022, 2021, 2020, 2016
Adoption of MSQ format to test multiple distinct decidability and closure assertions simultaneously without negative marking.
2022, 2021
Heavy reliance on standard decision problem tables (emptiness, universality, equivalence) across grammar classes (CFG vs Regular vs TM).
2025, 2017, 2016, 2014, 2013, 2012
Appeared as a direct, 1-mark foundational conceptual question testing basic definitions of countable vs uncountable infinite sets in automata theory.
2014
Testing conceptual closure properties via Multiple Select Questions (MSQ) where each option corresponds to a distinct formal language class under the same operation.
2023

Difficulty notes

Easy questions directly recall closure properties or standard entries in the decidability table (e.g., emptiness of CFG vs TM, definition of TM decider). Medium questions involve reasoning through many-one reductions with complementation, dovetailed simulation arguments to separate RE from non-RE, or identifying step-bounded deciders that bypass Rice's Theorem.