Turing Machine Decision Properties MCQs: 12 Solved Questions with Explanations

Every decision-properties question hides one fork: is the property a bound on how long the machine runs, or a property of the language it recognises? Bounds are decidable, because only a finite part of the input can matter. Language properties usually are not. Classify each of the 12 MCQs below as decidable (D), recognisable but undecidable (RE), or not even recognisable (not RE), then check yourself against the answer. More practice sits in GATE CS Exam Preparation.

Build the decision-properties map before solving

Name the fork first. A bound question fixes a step count, so only a bounded window of input and tape matters and a simulator settles it. A semantic question asks about L(M), the strings the machine accepts, and Rice's theorem bites: any property true of one recognisable language and false of another is undecidable for an arbitrary M. Rice's Theorem for GATE works that test out.

Take Sigma = {0,1} and k = 3. The head visits at most three cells in three steps, so two inputs agreeing on their first three symbols are indistinguishable, and the representatives are the strings of length three or less: epsilon, 0, 1, 00, 01, 10, 11, 000, 001, 010, 011, 100, 101, 110, 111, so 1 + 2 + 4 + 8 = 15 simulations settle it. Let M0 halt after two steps when the first symbol is 1 and loop otherwise: input 0 exceeds three steps, input 1 does not. Nothing depends on three, so the same window decides k = 2021.

Decision Properties MCQs 1-3: fixed bounds versus semantic properties

Question 1

For a Turing machine M, ⟨M⟩ denotes an encoding of M. Consider the following two languages.

L₁ = { ⟨M⟩ | M takes more than 2021 steps on all inputs }
L₂ = { ⟨M⟩ | M takes more than 2021 steps on some input }

Which one of the following options is correct?

• A. Both L₁ and L₂ are decidable.

• B. L₁ is decidable and L₂ is undecidable

• C. L₁ is undecidable and L₂ is decidable

• D. Both L₁ and L₂ are undecidable

Answer: A. In 2021 steps the head never leaves the first 2021 cells, so behaviour depends only on the first 2021 input symbols and the blanks past them. Simulating every string of length 2021 or less settles both the some-input and the all-inputs version, so both are decidable.

Question 2

Consider the following languages.

L₁ = { ⟨M⟩ | M takes at least 2016 steps on some input }

L₂ = { ⟨M⟩ | M takes at least 2016 steps on all inputs }

L₃ = { ⟨M⟩ | M accepts ε }

where for each Turing machine M, ⟨M⟩ denotes a specific encoding of M. Which one of the following is TRUE?

• A. L₁ is recursive and L₂, L₃ are not recursive

• B. L₂ is recursive and L₁, L₃ are not recursive

• C. L₁, L₂ are recursive and L₃ is not recursive

• D. L₁, L₂, L₃ are recursive

Answer: C. Finite-prefix simulation decides bounded L1/L2; unbounded epsilon acceptance makes L3 undecidable.

Question 3

Let ⟨M⟩ be the encoding of a Turing machine as a string over Σ = {0,1}. Let

L = { ⟨M⟩ | M is a Turing machine that accepts a string of length 2014 }.

Then L is:

• A. decidable and recursively enumerable

• B. undecidable but recursively enumerable

• C. undecidable and not recursively enumerable

• D. decidable but not recursively enumerable

Answer: B. There are 2^2014 strings of length 2014 over {0,1}. Dovetail M on all of them and an acceptance eventually shows up, so L is recursively enumerable. You can never conclude that none accepts, since a silent run may still be running. Accepting a length-2014 string is a nontrivial property of L(M), so Rice makes it undecidable.

Decision Properties MCQs 4-6: spot the undecidable language property

Question 4

Which of the following languages are undecidable? Note that ⟨M⟩ indicates encoding of the Turing machine M.

L₁ = { ⟨M⟩ | L(M) = ∅ }

L₂ = { ⟨M,w,q⟩ | M on input w reaches state q in exactly 100 steps }

L₃ = { ⟨M⟩ | L(M) is not recursive }

L₄ = { ⟨M⟩ | L(M) contains at least 21 members }

• A. L₁, L₃, and L₄ only

• B. L₁ and L₃ only

• C. L₂ and L₃ only

• D. L₂, L₃, and L₄ only

Answer: A. Simulating 100 steps decides L2; Rice makes L1/L3/L4 undecidable. Only time is bounded.

Question 5

Consider the following problems. 𝐿(𝐺) denotes the language generated by a grammar 𝐺. 𝐿(𝑀) denotes the language accepted by a machine 𝑀.

(I) For an unrestricted grammar 𝐺 and a string 𝑤, whether 𝑤 ∈ 𝐿(𝐺)

(II) Given a Turing machine M, whether L(M) is regular

(III) Given two grammars 𝐺1 and 𝐺2, whether 𝐿(𝐺1) = 𝐿(𝐺2)

(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?

• A. Only I and II are undecidable

• B. Only III is undecidable

• C. Only II and IV are undecidable

• D. Only I, II and III are undecidable

Answer: D. An unrestricted grammar is Turing-equivalent, so I is Turing-machine membership; II asks whether L(M) is regular, a nontrivial property; III is grammar equivalence. All three are undecidable. IV is easy rather than hard: determinise the NFA, then read the DFA as a DPDA that never touches its stack, so the answer is always yes.

Question 6

Let L(R) be the language represented by regular expression R. Let L(G) be the language generated by a context free grammar G. Let L(M) be the language accepted by a Turing machine M. Which of the following decision problems are undecidable?

I. Given a regular expression R and a string w, is w ∈ L(R)?

II. Given a context-free grammar G, is L(G) = ∅

III. Given a context-free grammar G, is L(G) = Σ* for some alphabet Σ ?

IV. Given a Turing machine M and a string w, is w ∈ L(M)?

• A. I and IV only

• B. II and III only

• C. II, III and IV only

• D. III and IV only

Answer: D. Simulation decides I; productive marking decides II. CFG universality and TM acceptance make III/IV undecidable.

Decision Properties MCQs 7-9: recognisable languages and complements

Question 7

Which of the following decision problems are undecidable?

I. Given NFAs N₁ and N₂, is L(N₁) ∩ L(N₂) = ∅ ?

II. Given a CFG G = (N,Σ,P,S) and a string x ∈ Σ*, does x ∈ L(G)?

III. Given CFGs G₁ and G₂, is L(G₁) = L(G₂)?

IV. Given a TM M, is L(M) = Φ?

• A. I and IV only

• B. II and III only

• C. III and IV only

• D. II and IV only

Answer: C. Product reachability decides I; parsing decides II. CFG equivalence and TM emptiness make III/IV undecidable.

Question 8

Define languages L0 and L1 as follows :

L0 = {< M, w, 0 > | M halts on w}

L1 = {< M, w, 1 > | M does not halts on w}

Here < M, w, i > is a triplet, whose first component. M is an encoding of a Turing Machine, second component, w, is a string, and third component, i, is a bit. Let L = L0 ∪ L1. Which of the following is true ?

• A. L is recursively enumerable, but L' is not

• B. L' is recursively enumerable, but L is not

• C. Both L and L' are recursive

• D. Neither L nor L' is recursively enumerable

Answer: D. Suppose L were recursively enumerable. Keeping only the triples whose last bit is 1 is a decidable filter, so the non-halting set would be recursively enumerable, which it is not. If L' were recursively enumerable its last-bit-0 triples give the same contradiction. Neither is recursively enumerable.

Question 9

Let L1 be a recursive language, and let L2 be a recursively enumerable but not a recursive language. Which one of the following is TRUE?

L1' --> Complement of L1

L2' --> Complement of L2

• A. L1' is recursive and L2' is recursively enumerable

• B. L1' is recursive and L2' is not recursively enumerable

• C. L1' and L2' are recursively enumerable

• D. L1' is recursively enumerable and L2' is recursive

Answer: B. Recursive languages are complement-closed. Dovetailing RE L2' with L2 would decide L2, a contradiction.

Decision Properties MCQs 10-12: dovetailing, syntax checks and reductions

Question 10

If L and L' are recursively enumerable, then L is

• A. regular

• B. context-free

• C. context-sensitive

• D. recursive

Answer: D. Dovetail the two recognisers, alternating their steps. Every string lies in exactly one of L and L', so one recogniser must accept, and that decides membership. Nothing forces L to be regular or context-free.

Question 11

Which of the following are decidable?

I. Whether the intersection of two regular languages is infinite

II. Whether a given context-free language is regular

III. Whether two push-down automata accept the same language

IV. Whether a given grammar is context-free

• A. I and II

• B. I and IV

• C. II and III

• D. II and IV

Answer: B. For I, take the product automaton and look for a cycle reachable from the start state that can still reach an accepting state; that decides infiniteness. IV is a syntax check: a grammar is context-free exactly when every production has one nonterminal on its left. II and III are undecidable.

Question 12

X ≤m Y denotes that a language X is mapping reducible to language Y. Given that X ≤m Y and Y ≤m Z. Consider the statements given below S1: If Z is decidable then X and Y are decidable. S2: If Y is decidable then X and Z are decidable. S3 If Z is undecidable then X and Y are undecidable. S4 If X is decidable then Y and Z are decidable. Which of the above statements are TRUE?

• A. Only S1 and S3

• B. Only S2 and S4

• C. Only S1

• D. Only S3

Answer: C. A mapping reduction pushes decidability backwards along the arrow: a decider for Z gives one for Y, and then one for X. That is S1, and only S1.

The counterexample kills the other three at once. Take X = Y = {0} and Z = HALT. {0} reduces to itself by identity, and to HALT by sending 0 to a machine that halts on epsilon and everything else to one that loops. So X and Y are decidable while Z is not, refuting S2 and S4 (both need Z decidable) and S3 (it needs X and Y undecidable).

Review: four tests that classify all twelve questions

1. Bound the clock. A fixed step count makes only a finite window of the input relevant, so simulate the finitely many cases. (Question 1; L1, L2 in 2; L2 in 4.)

2. Ask about the language, not the run. Any nontrivial property of L(M) is undecidable, and acceptance and halting sit underneath it. (Question 3; L1, L3, L4 in 4; I to III in 5; IV in 6 and 7; Question 8.)

3. Drop below Turing machines. Automata and grammars can be analysed instead of run, so membership, emptiness and infiniteness are decidable; only equivalence and universality stay undecidable. (IV in 5; I to III in 6 and 7; Question 11.)

4. Read the closure rules. A recognisable language whose complement is also recognisable is recursive (Questions 9, 10), and decidability travels backwards along a reduction, never forwards (Question 12).

The short version and next practice route

The short version: a step bound makes a question decidable, a property of the accepted language makes it undecidable, and a recognisable language whose complement is also recognisable is recursive. If your calls went wrong on Questions 1, 3, 8 or 12, redo those unaided, then widen out with Theory of Computation MCQs. GATE Guidance by Sanchit Sir teaches the automata track in order; GATE Test Series shows whether you are fast enough.