High yield ●●●

🚫 Decidability & Undecidability

Why it matters: Halting problem, reductions and Rice's theorem: guaranteed conceptual questions.

Subtopics

Each subtopic has its own page: idea, why, how, example, play, check. Mark each one understood when it clicks. 0 of 4 done.

Formulas

A_TM
RE, undecidable; its complement is not RE
Reduction rules
A ≤ B and B decidable ⇒ A decidable; A ≤ B and A undecidable ⇒ B undecidable
Rice
non-trivial property P of L(M) ⇒ {⟨M⟩ : L(M) has P} undecidable
RE tests
L RE ⇔ some TM enumerates it ⇔ accepts it

What GATE asks from this

Question types seen repeatedly in past papers. More stars means more frequent.

★★★
Which problems are decidable?
Pick from lists about DFAs, CFGs and TMs; use Rice for TM-property questions.
★★★
Apply reductions correctly
If L₁ ≤ L₂ and L₂ is decidable/RE, what follows for L₁? Direction traps.
★★★
Recursive / RE classification
Is the language recursive, RE not recursive, or not RE?
★★★
Rice's theorem applicability
Which properties does Rice cover, and which are decidable anyway?

Ratings are approximate, based on recurring patterns in past GATE CSE papers.

Previous year questions

7 real questions from the official GATE CSE papers (2013 to 2022), newest first, each with the official answer key and a worked solution. Questions are the property of the GATE organising institutes; this copy is for your personal study.

7 questions · 0 correct of 0 attempted · marks 0 / 12

Year:
GATE 2022 · Q46MSQ2 marks
Which of the following is/are undecidable?

One or more options may be correct. Select all that apply, then submit.

GATE 2021 Set 1 · Q12MSQ1 mark
Let ⟨M⟩ denote an encoding of an automaton M. Suppose that Σ = {0, 1}. Which of the following languages is/are NOT recursive?

One or more options may be correct. Select all that apply, then submit.

GATE 2021 Set 1 · Q39MCQ2 marks
For a Turing machine M, ⟨M⟩ denotes an encoding of M. Consider the following two languages. L1 = { ⟨M⟩ | M takes more than 2021 steps on all inputs } and L2 = { ⟨M⟩ | M takes more than 2021 steps on some input }. Which one of the following options is correct?
GATE 2020 · Q26MCQ2 marks
Which of the following languages are undecidable? Note that ⟨M⟩ indicates encoding of the Turing machine M. L1 = { ⟨M⟩ | L(M) = ∞ }, L2 = { ⟨M, w, q⟩ | M on input w reaches state q in exactly 100 steps }, L3 = { ⟨M⟩ | L(M) is not recursive }, L4 = { ⟨M⟩ | L(M) contains at least 21 members }.
GATE 2018 · Q36MCQ2 marks
Consider the following problems. L(G) denotes the language generated by a grammar G. L(M) denotes the language accepted by a machine M.
(I) For an unrestricted grammar G and a string w, whether w ∈ L(G).
(II) Given a Turing machine M, whether L(M) is regular.
(III) Given two grammars G1 and G2, whether L(G1) = L(G2).
(IV) Given an NFA N, whether there is a deterministic PDA P such that N and P accept the same language. Which one of the following statements is correct?
GATE 2016 Set 1 · Q17MCQ1 mark
Which of the following decision problems are undecidable? I. Given NFAs N1 and N2, is L(N1) ∩ L(N2) = Φ? II. Given a CFG G = (N, Σ, P, S) and a string x ∈ Σ*, does x ∈ L(G)? III. Given CFGs G1 and G2, is L(G1) = L(G2)? IV. Given a TM M, is L(M) = Φ?
GATE 2013 Code A · Q41MCQ2 marks
Which of the following is/are undecidable?
1. G is a CFG. Is L(G) = Φ?
2. G is a CFG. Is L(G) = Σ*?
3. M is a Turing machine. Is L(M) regular?
4. A is a DFA and N is an NFA. Is L(A) = L(N)?

Common traps

Rice talks about L(M), not about M's code or running time.
"M takes more than k steps on some input" is decidable (simulate on short inputs).
Reductions only transfer undecidability from the source to the target.
Undecidable does not mean unrecognisable: A_TM is RE.