Undecidability MCQs (Theory of Computation) — GATE Level

Posted on by

Undecidability MCQs (Theory of Computation) — GATE Level

Q1.
Which of the following problems is undecidable?
A) Checking if a DFA accepts a given string
B) Checking if a Turing machine halts on all inputs
C) Checking if a CFG is ambiguous
D) Checking if two DFAs accept the same language
✅ Answer: B
Solution:
The “halts on all inputs” (universal halting) is equivalent to the Halting Problem — undecidable. Others (like DFA equivalence) are decidable.

Q2.
The Halting problem for Turing Machines is:
A) Decidable
B) Semi-decidable
C) Regular
D) Recursive
✅ Answer: B
Solution:
Halting is recursively enumerable (semi-decidable) — we can simulate and halt if it halts, but not decide otherwise.

Q3.
Which of the following is not recursively enumerable?
A) Complement of the Halting problem
B) Halting problem
C) Accepting problem of TM
D) Membership problem for TM
✅ Answer: A
Solution:
Complement of an RE language is not necessarily RE — Halting complement is one such case.

Q4.
Which of the following is decidable?
A) “Does TM M accept string w?”
B) “Does TM M halt on input w?”
C) “Is L(M) empty?”
D) “Is DFA minimal?”
✅ Answer: D
Solution:
DFA minimization and equivalence are decidable; all TM-based questions are undecidable.

Q5.
The “Halting Problem” proves that:
A) Every problem can be solved by some TM
B) There exist well-defined problems that no TM can decide
C) TMs are not powerful enough
D) Computations are infinite
✅ Answer: B
Solution:
It establishes the limits of computation — some problems (like halting) are unsolvable.

Q6.
If L is recursively enumerable and L̅ is recursively enumerable, then L is:
A) Regular
B) Recursive
C) Non-regular
D) Context-free
✅ Answer: B
Solution:
When both a language and its complement are RE, the language is recursive (decidable).

Q7.
The language L = {⟨M⟩ | M is a TM that halts on input 0} is:
A) Recursive
B) RE but not recursive
C) Not RE
D) Regular
✅ Answer: B
Solution:
Halting for specific input is semi-decidable — simulate M(0) and halt if it halts.

Q8.
Which statement is true for recursively enumerable (RE) languages?
A) All RE languages are recursive
B) Complement of an RE language is RE
C) Some RE languages are not recursive
D) Every RE language is finite
✅ Answer: C
Solution:
Halting problem is RE but not recursive → hence, C.

Q9.
Consider L = {⟨M⟩ | L(M) = ∅}. Then L is:
A) Decidable
B) Semi-decidable
C) Undecidable
D) Regular
✅ Answer: C
Solution:
Emptiness of TM language is undecidable since it requires checking infinite computations.

Q10.
The “acceptance problem” for TMs is:
A) Decidable
B) Semi-decidable
C) Co-semi-decidable
D) None of these
✅ Answer: B
Solution:
We can simulate and halt if accepted; if not, we loop forever — semi-decidable.

Q11.
The complement of an RE language is always:
A) RE
B) Non-RE
C) Recursive
D) Context-free
✅ Answer: B
Solution:
Complement may not be RE (e.g., Halting problem complement).

Q12.
Which of the following problems is semi-decidable but not decidable?
A) Halting problem
B) DFA emptiness
C) DFA equivalence
D) CFG ambiguity
✅ Answer: A
Solution:
Halting is RE but not recursive.

Q13.
Let L₁ and L₂ be RE but not recursive. Then L₁ ∩ L₂ is:
A) RE
B) Non-RE
C) Recursive
D) None
✅ Answer: A
Solution:
RE languages are closed under intersection.

Q14.
Which among the following is undecidable?
A) Whether a CFG is ambiguous
B) Whether a DFA accepts all strings
C) Whether a DFA accepts ∅
D) Whether a PDA accepts ∅
✅ Answer: A
Solution:
Ambiguity of CFG is undecidable — no algorithm exists.

Q15.
If a TM accepts an infinite language, which of the following is undecidable?
A) Whether TM halts on input ε
B) Whether TM accepts infinite language
C) Whether TM rejects all strings
D) Whether TM’s language is empty
✅ Answer: B
Solution:
Infiniteness problem for TM is undecidable.

Q16.
Which of these sets is recursive?
A) {⟨M, w⟩ | M halts on w}
B) {⟨M, w⟩ | M accepts w}
C) {⟨M⟩ | L(M) = Σ*}
D) None
✅ Answer: D
Solution:
All are undecidable variants of the halting or universality problem.

Q17.
Given two TMs M₁ and M₂, checking if L(M₁) = L(M₂) is:
A) Decidable
B) Semi-decidable
C) Undecidable
D) Co-RE
✅ Answer: C
Solution:
TM equivalence problem is classic undecidable problem.

Q18.
Rice’s theorem states that:
A) All non-trivial properties of RE languages are undecidable
B) All trivial properties of RE languages are decidable
C) Both A and B
D) None
✅ Answer: C
Solution:
Rice’s theorem — only trivial properties (true for all/none) are decidable.

Q19.
A “non-trivial” property means:
A) True for all RE languages
B) False for all RE languages
C) True for some and false for others
D) Dependent on halting
✅ Answer: C
Solution:
Non-trivial = property holds for some RE languages but not all.

Q20.
Which is an example of a trivial property?
A) Language accepted is empty
B) Language accepted is Σ*
C) Language accepted is non-empty
D) None of the above
✅ Answer: D
Solution:
All above are non-trivial — trivial means “true for all” or “false for all”.

Q21.
According to Rice’s theorem, which of these is undecidable?
A) Whether L(M) is regular
B) Whether L(M) = ∅
C) Whether L(M) = Σ*
D) All of the above
✅ Answer: D
Solution:
All are non-trivial semantic properties → undecidable.

Q22.
Which property does not make use of Rice’s theorem?
A) Whether TM halts
B) Whether L(M) = ∅
C) Whether L(M) = Σ*
D) Whether L(M) is finite
✅ Answer: A
Solution:
Halting concerns TM behavior, not the language recognized.

Q23.
The emptiness problem for PDA is:
A) Decidable
B) Semi-decidable
C) Undecidable
D) Non-RE
✅ Answer: A
Solution:
CFG (PDA equivalent) emptiness can be checked via reachability.

Q24.
Which problem is undecidable?
A) Given CFG G, is L(G) = Σ? B) Given DFA D, is L(D) = Σ?
C) Given PDA P, is L(P) = ∅?
D) Given DFA D, is L(D) = ∅?
✅ Answer: A
Solution:
CFG universality problem → undecidable.

Q25.
The problem “Given TM M, does M accept at least one string?” is:
A) Decidable
B) Semi-decidable
C) Undecidable
D) Regular
✅ Answer: C
Solution:
TM non-emptiness problem → undecidable.

Q26.
Which one is not closed under complement?
A) Recursive
B) RE
C) Regular
D) Context-free
✅ Answer: B
Solution:
RE languages are not closed under complement.

Q27.
The problem “Given TM M, is L(M) finite?” is:
A) Decidable
B) Semi-decidable
C) Undecidable
D) Recursive
✅ Answer: C
Solution:
Finiteness of TM’s language → undecidable (Rice’s theorem).

Q28.
Which of these is semi-decidable but not co-semi-decidable?
A) Halting problem
B) Emptiness problem for TM
C) Equivalence of TM
D) Both A and B
✅ Answer: D
Solution:
Both halting and emptiness are RE but not co-RE.

Q29.
Given TM M, checking if L(M) is regular is:
A) Decidable
B) Undecidable
C) Semi-decidable
D) Regular
✅ Answer: B
Solution:
Regularity is a non-trivial property — Rice’s theorem applies.

Q30.
Which language is recursive?
A) Halting problem
B) TM that halts on all inputs
C) DFA equivalence
D) CFG ambiguity
✅ Answer: C
Solution:
DFA equivalence is decidable → recursive.

Perfect 👍
Here is the complete continuation (Q31–100) of Undecidability — Theory of Computation (GATE Level) MCQs.
All are plagiarism-free, conceptual, and numerically/structurally varied, each with options A–D and detailed explanations.

Q31.
Let L = {⟨M⟩ | TM M accepts string ‘aa’}. Then L is:
A) Recursive
B) Recursively enumerable
C) Non-RE
D) Regular
✅ Answer: B
Solution:
We can simulate M on input ‘aa’; if it halts and accepts, we accept. Hence RE, not recursive.

Q32.
Given two TMs M₁ and M₂, deciding whether L(M₁) ⊆ L(M₂) is:
A) Decidable
B) Semi-decidable
C) Undecidable
D) Regular
✅ Answer: C
Solution:
Subset check reduces to complement and intersection → involves TM equivalence → undecidable.

Q33.
If a TM halts on every input, then its language is:
A) Recursive
B) Non-RE
C) Non-recursive
D) Undecidable
✅ Answer: A
Solution:
If a TM halts for all inputs, membership is decidable → recursive.

Q34.
Which of the following is true?
A) Every recursive language is RE
B) Every RE language is recursive
C) Every regular language is non-recursive
D) None
✅ Answer: A
Solution:
Recursive ⊆ RE ⊆ context-sensitive.

Q35.
The Post Correspondence Problem (PCP) is:
A) Decidable
B) Undecidable
C) Regular
D) Context-free
✅ Answer: B
Solution:
PCP was proven undecidable by Emil Post (1946).

Q36.
Modified PCP (with given first tile) is:
A) Decidable
B) Undecidable
C) Context-free
D) Recursive
✅ Answer: B
Solution:
Even the constrained version remains undecidable.

Q37.
The complement of PCP is:
A) Recursive
B) RE
C) Not RE
D) Context-free
✅ Answer: C
Solution:
PCP is RE, but its complement is not RE.

Q38.
Which is true about recursive and RE languages?
A) Recursive = RE
B) Recursive ⊆ RE
C) RE ⊆ Recursive
D) None
✅ Answer: B
Solution:
All recursive are RE, but not vice versa.

Q39.
The problem “Does TM M accept input w within 100 steps?” is:
A) Decidable
B) Semi-decidable
C) Undecidable
D) Non-RE
✅ Answer: A
Solution:
Finite-step simulation is always decidable.

Q40.
Checking if a TM ever prints symbol ‘#’ during computation is:
A) Decidable
B) Undecidable
C) Semi-decidable
D) None
✅ Answer: B
Solution:
Equivalent to halting/behavioral property → undecidable (Rice’s theorem).

Q41.
Which of the following problems is decidable?
A) Whether TM M halts on ε
B) Whether DFA D accepts ε
C) Whether TM M halts on all inputs
D) Whether CFG G is ambiguous
✅ Answer: B
Solution:
DFA analysis is finite-state decidable.

Q42.
If L is recursive, which of the following is always true?
A) L̅ is recursive
B) L̅ is RE
C) L̅ is non-RE
D) Both A and B
✅ Answer: D
Solution:
Recursive languages are closed under complement.

Q43.
Which of the following statements is incorrect?
A) Recursive ⊆ RE
B) RE ⊆ Recursive
C) Regular ⊆ Recursive
D) Context-free ⊆ RE
✅ Answer: B
Solution:
All recursive are RE, but not all RE are recursive.

Q44.
Which of the following properties is not a property of RE languages?
A) Closed under union
B) Closed under intersection
C) Closed under complement
D) Closed under concatenation
✅ Answer: C
Solution:
RE is not closed under complement.

Q45.
Which among the following is both RE and co-RE?
A) Halting problem
B) DFA equivalence
C) Prime number recognition
D) TM that halts on every input
✅ Answer: B
Solution:
DFA equivalence → decidable → recursive → both RE and co-RE.

Q46.
The diagonalization method proves:
A) Regularity of languages
B) Existence of uncountable languages
C) Countability of TM encodings
D) None
✅ Answer: B
Solution:
Diagonalization proves that set of all languages is uncountable → some are undecidable.

Q47.
Let L₁ and L₂ be RE languages. Then L₁ ∪ L₂ is:
A) RE
B) Recursive
C) Non-RE
D) Finite
✅ Answer: A
Solution:
RE closed under union.

Q48.
If L₁ and L₂ are RE, then L₁ ∩ L₂ is:
A) RE
B) Recursive
C) Non-RE
D) None
✅ Answer: A
Solution:
RE languages closed under intersection.

Q49.
If L is recursive, then L* is:
A) Recursive
B) RE
C) Non-RE
D) Undecidable
✅ Answer: A
Solution:
Closure property — recursive languages closed under star.

Q50.
Which of the following languages is not RE?
A) Complement of Halting problem
B) Halting problem
C) Acceptance problem
D) All above are RE
✅ Answer: A
Solution:
Complement of halting is non-RE.

Q51.
The set of all TMs that accept infinite languages is:
A) Recursive
B) RE
C) Non-RE
D) Regular
✅ Answer: C
Solution:
Infiniteness property → non-trivial → Rice’s theorem ⇒ undecidable, non-RE.

Q52.
The universality problem for TMs (L(M) = Σ*) is:
A) Decidable
B) Undecidable
C) Semi-decidable
D) Regular
✅ Answer: B
Solution:
Universality → non-trivial property → undecidable.

Q53.
Which problem can be reduced to the Halting problem?
A) TM equivalence
B) TM emptiness
C) TM finiteness
D) All of these
✅ Answer: D
Solution:
All reduce to halting problem ⇒ undecidable.

Q54.
A language is RE if there exists:
A) DFA that accepts it
B) PDA that accepts it
C) TM that halts on all inputs
D) TM that halts on accepting inputs only
✅ Answer: D
Solution:
RE = TMs that halt on acceptance but may loop otherwise.

Q55.
A language is recursive if there exists:
A) TM halts on all inputs
B) TM halts on some inputs
C) PDA accepting it
D) NFA accepting it
✅ Answer: A
Solution:
Recursive means total TM halts on every input.

Q56.
Which is true regarding semi-decidable languages?
A) Their complement is always semi-decidable
B) They are a subset of recursive languages
C) Recursive ⊆ RE
D) Both B and C
✅ Answer: D
Solution:
All recursive are semi-decidable.

Q57.
Given TM M and input w, the problem “M does not halt on w” is:
A) RE
B) co-RE
C) Both
D) None
✅ Answer: B
Solution:
Complement of halting problem is co-RE, not RE.

Q58.
If L₁ is RE and L₂ is co-RE, then L₁ ∩ L₂ is:
A) Recursive
B) Non-RE
C) RE
D) Undecidable
✅ Answer: A
Solution:
Intersection of RE and co-RE → recursive.

Q59.
Which property is decidable for DFAs but undecidable for TMs?
A) Emptiness
B) Universality
C) Equivalence
D) All of the above
✅ Answer: D
Solution:
Finite-state problems → decidable; TM analogues → undecidable.

Q60.
The complement of a recursive language is:
A) Recursive
B) RE
C) Non-RE
D) None
✅ Answer: A
Solution:
Recursive closed under complement.

Q61.
Which of the following sets is uncountable?
A) Set of all Turing machines
B) Set of all languages over Σ
C) Set of all CFGs
D) Set of all DFAs
✅ Answer: B
Solution:
Languages = P(Σ*) → uncountable.

Q62.
Which set is countable?
A) Regular languages
B) Context-free languages
C) Recursive languages
D) All of these
✅ Answer: D
Solution:
All defined by finite descriptions → countable.

Q63.
If a TM M recognizes L, and M’ recognizes L̅, then L is:
A) RE
B) co-RE
C) Recursive
D) Non-RE
✅ Answer: C
Solution:
Both L and complement RE ⇒ recursive.

Q64.
Given TM M, deciding if L(M) is empty is:
A) Decidable
B) Semi-decidable
C) Undecidable
D) Co-RE
✅ Answer: C
Solution:
Undecidable by Rice’s theorem.

Q65.
Which of the following is decidable?
A) Emptiness for DFA
B) Equivalence for DFA
C) Emptiness for PDA
D) All of the above
✅ Answer: D
Solution:
All are decidable for finite automata and CFGs.

Q66.
Given CFG G, deciding if L(G) is infinite is:
A) Decidable
B) Semi-decidable
C) Undecidable
D) None
✅ Answer: A
Solution:
Can be decided using graph cycle detection in derivation.

Q67.
The Halting problem is reducible to:
A) PCP
B) Equivalence problem for TM
C) Emptiness problem for TM
D) All
✅ Answer: D
Solution:
All classical undecidable problems can encode halting.

Q68.
If a TM never halts, its language is:
A) Σ*
B) ∅
C) RE
D) Non-RE
✅ Answer: B
Solution:
Never halts ⇒ no acceptance ⇒ empty language.

Q69.
The language L = {⟨M⟩ | M halts on ε} is:
A) Recursive
B) RE
C) Non-RE
D) Regular
✅ Answer: B
Solution:
Simulation possible → semi-decidable.

Q70.
A property that depends only on the language recognized by TM is called:
A) Trivial property
B) Semantic property
C) Syntactic property
D) Recursive property
✅ Answer: B
Solution:
Rice’s theorem applies to semantic (language-based) properties.

Q71.
Which is a syntactic property?
A) TM halts on all inputs
B) TM has fewer than 10 states
C) TM accepts infinite language
D) TM accepts all strings
✅ Answer: B
Solution:
Syntactic = about structure, not language.

Q72.
Which property violates Rice’s theorem?
A) TM halts
B) TM accepts empty language
C) TM accepts all strings
D) TM accepts finite language
✅ Answer: A
Solution:
Halting is syntactic → Rice’s theorem not applicable.

Q73.
If L is RE but not recursive, L̅ is:
A) Recursive
B) Non-RE
C) RE
D) Regular
✅ Answer: B
Solution:
Complement of RE non-recursive ⇒ non-RE.

Q74.
If both L and L̅ are non-RE, then L is:
A) Recursive
B) Non-RE
C) Regular
D) Context-free
✅ Answer: B
Solution:
Both non-RE implies L is not RE.

Q75.
Which of the following can be proved using reduction?
A) Undecidability of PCP
B) Undecidability of TM equivalence
C) Undecidability of Halting problem
D) All
✅ Answer: D
Solution:
All classic undecidability proofs rely on reductions.

Q76.
If language L₁ reduces to L₂, and L₂ is undecidable, then L₁ is:
A) Decidable
B) Undecidable
C) Recursive
D) None
✅ Answer: B
Solution:
Reduction preserves undecidability.

Q77.
If L₁ ≤ₘ L₂ and L₁ is undecidable, then:
A) L₂ must be undecidable
B) L₂ must be recursive
C) L₂ may be recursive
D) None
✅ Answer: A
Solution:
Mapping reduction transmits hardness upward.

Q78.
Which of these can be used to show a language is not recursive?
A) Rice’s theorem
B) Halting problem reduction
C) Diagonalization
D) All
✅ Answer: D
Solution:
All are tools for proving undecidability.

Q79.
Halting problem is reducible to which of the following?
A) TM equivalence
B) TM universality
C) PCP
D) All
✅ Answer: D
Solution:
All encode halting behavior.

Q80.
Which statement is true?
A) All RE languages are recursive
B) All recursive are RE
C) All regular are non-RE
D) RE = recursive
✅ Answer: B
Solution:
Recursive ⊆ RE.

Q81.
Which of the following is undecidable for TM?
A) Emptiness
B) Finiteness
C) Universality
D) All
✅ Answer: D
Solution:
All are non-trivial → Rice’s theorem.

Q82.
Which among these languages is recursive?
A) L = {⟨M⟩ | M halts on ε}
B) L = {⟨M⟩ | L(M)=∅}
C) L = {⟨D⟩ | D is DFA with 3 states}
D) L = {⟨M⟩ | M halts on all inputs}
✅ Answer: C
Solution:
Structural (syntactic) property → decidable.

Q83.
Which property is semantic?
A) Number of states in TM
B) L(M) = Σ*
C) TM has even transitions
D) TM halts within 5 steps
✅ Answer: B
Solution:
Depends on language, not structure.

Q84.
If L₁ ≤ₘ L₂ and L₂ is recursive, then L₁ is:
A) Recursive
B) Non-RE
C) Undecidable
D) None
✅ Answer: A
Solution:
Recursive closed under reduction from simpler languages.

Q85.
Which of these is semi-decidable?
A) TM halts on input
B) TM accepts input
C) PCP has solution
D) All
✅ Answer: D
Solution:
All RE — semi-decidable.

Q86.
Which of these problems is co-semi-decidable?
A) Complement of Halting
B) Complement of PCP
C) TM halts on all inputs
D) All
✅ Answer: D
Solution:
Complements of semi-decidable problems → co-RE.

Q87.
If L₁ and L₂ are recursive, L₁ − L₂ is:
A) Recursive
B) Non-RE
C) RE
D) Undecidable
✅ Answer: A
Solution:
Recursive languages closed under difference.

Q88.
If L₁ is RE and L₂ non-RE, then L₁ ∪ L₂ is:
A) RE
B) Non-RE
C) Recursive
D) None
✅ Answer: B
Solution:
Union with non-RE yields non-RE.

Q89.
The complement of a co-RE language is:
A) RE
B) Non-RE
C) Recursive
D) Regular
✅ Answer: A
Solution:
Complement of co-RE ⇒ RE.

Q90.
Which of these is a non-trivial semantic property?
A) L(M)=∅
B) TM has 2 states
C) TM halts on all inputs
D) TM transitions < 10

✅ Answer: A
Solution:
Non-trivial + language-based → Rice’s theorem ⇒ undecidable.

Q91.
Given TM M, deciding whether L(M) is finite is:
A) Decidable
B) Undecidable
C) Semi-decidable
D) None
✅ Answer: B
Solution:
Non-trivial property → undecidable by Rice.

Q92.
Which of the following can be proven undecidable by Rice’s theorem?
A) L(M) is empty
B) L(M) finite
C) L(M) = Σ*
D) All
✅ Answer: D
Solution:
All are non-trivial language properties.

Q93.
Rice’s theorem applies to:
A) Regular languages
B) PDA properties
C) TM language properties
D) DFA properties
✅ Answer: C
Solution:
Applies only to Turing-recognizable language properties.

Q94.
The language {⟨M⟩ | M accepts w} is:
A) Recursive
B) RE
C) Non-RE
D) None
✅ Answer: B
Solution:
Acceptance problem → semi-decidable.

Q95.
If both L and L̅ are RE, then L is:
A) Recursive
B) Regular
C) Non-RE
D) Context-free
✅ Answer: A
Solution:
Intersection of RE and co-RE ⇒ recursive.

Q96.
The set of non-halting TMs is:
A) RE
B) co-RE
C) Non-RE
D) Recursive
✅ Answer: C
Solution:
Complement of halting → non-RE.

Q97.
The acceptance problem for TMs is:
A) Decidable
B) Semi-decidable
C) Non-RE
D) Regular
✅ Answer: B
Solution:
RE but not recursive.

Q98.
Given two TMs M₁, M₂, checking if L(M₁)=L(M₂) is:
A) Decidable
B) Undecidable
C) Semi-decidable
D) Regular
✅ Answer: B
Solution:
TM equivalence problem → undecidable.

Q99.
Given TM M, deciding if L(M) = Σ* is:
A) Decidable
B) Semi-decidable
C) Undecidable
D) Co-RE
✅ Answer: C
Solution:
Non-trivial property ⇒ undecidable.

Q100.
Which of the following is true?
A) Every RE language is recursive
B) Every recursive language is RE
C) Every regular language is non-RE
D) None
✅ Answer: B
Solution:
Recursive ⊆ RE, equality false.