Q.1 Which of the following problems is undecidable?
Halting Problem
Sorting Problem
Greatest Common Divisor Problem
Shortest Path Problem
Explanation - The Halting Problem, posed by Alan Turing, is undecidable because no algorithm can determine for all programs whether they halt or run forever.
Correct answer is: Halting Problem
Q.2 The Halting Problem is undecidable because:
It requires exponential time
It leads to contradiction when assuming a decider exists
It cannot be expressed in logic
It uses infinite memory
Explanation - Proof by contradiction shows that if a Halting decider existed, it could be used to construct a paradoxical program, proving no such decider exists.
Correct answer is: It leads to contradiction when assuming a decider exists
Q.3 Which of the following is a classic example of an undecidable problem?
Traveling Salesman Problem
Boolean Satisfiability Problem (SAT)
Post Correspondence Problem (PCP)
Maximum Flow Problem
Explanation - PCP was proven undecidable by Emil Post and is a fundamental problem in the theory of computation.
Correct answer is: Post Correspondence Problem (PCP)
Q.4 The Entscheidungsproblem (decision problem) posed by Hilbert is:
Decidable
Undecidable
NP-complete
PSPACE-complete
Explanation - Church and Turing independently proved Hilbert’s Entscheidungsproblem undecidable, showing that no algorithm can decide all first-order logic statements.
Correct answer is: Undecidable
Q.5 Which technique is commonly used to prove undecidability?
Reduction
Dynamic Programming
Greedy Algorithm
Backtracking
Explanation - Undecidability proofs usually involve reducing a known undecidable problem to another problem, showing that solving the latter would also solve the former.
Correct answer is: Reduction
Q.6 The Halting Problem was first introduced by:
Kurt Gödel
Alan Turing
Alonzo Church
Emil Post
Explanation - Alan Turing introduced the Halting Problem in 1936 as part of his foundational work on computation.
Correct answer is: Alan Turing
Q.7 Which of the following problems is undecidable for Turing Machines?
Whether a TM halts on all inputs
Whether a TM halts on a specific input
Whether a TM is deterministic
Whether a TM has finite states
Explanation - Determining if a Turing Machine halts on all possible inputs is undecidable, known as the universal halting problem.
Correct answer is: Whether a TM halts on all inputs
Q.8 Post Correspondence Problem (PCP) is undecidable because:
It requires exponential time
It can encode the Halting Problem
It uses non-deterministic transitions
It has infinitely many solutions
Explanation - PCP is undecidable because it can simulate computations and encode the Halting Problem within its structure.
Correct answer is: It can encode the Halting Problem
Q.9 Which of the following logic systems has been proven undecidable?
First-order logic
Propositional logic
Monadic predicate logic without equality
Boolean logic
Explanation - The validity problem in first-order logic is undecidable, as shown by Church and Turing.
Correct answer is: First-order logic
Q.10 The Rice’s theorem states:
All non-trivial properties of Turing machine languages are undecidable
Every Turing machine halts eventually
Every recursive function is computable
Finite automata cannot recognize regular languages
Explanation - Rice’s theorem proves that any non-trivial semantic property of Turing machine-recognized languages is undecidable.
Correct answer is: All non-trivial properties of Turing machine languages are undecidable
Q.11 Which of the following is NOT undecidable?
Halting Problem
Post Correspondence Problem
Regular Language Membership
Validity of First-order logic
Explanation - Checking membership in a regular language is decidable using finite automata.
Correct answer is: Regular Language Membership
Q.12 Which type of reduction is often used in proving undecidability?
Polynomial-time reduction
Mapping reduction
Linear reduction
Approximation reduction
Explanation - Mapping reduction is a method to show undecidability by transforming instances of one problem into another.
Correct answer is: Mapping reduction
Q.13 The language L = {⟨M⟩ | M is a TM that halts on input ε} is:
Decidable
Undecidable
NP-complete
Regular
Explanation - Determining whether a TM halts on the empty string is equivalent to solving the Halting Problem.
Correct answer is: Undecidable
Q.14 Which undecidable problem is directly related to program verification?
Halting Problem
Sorting Problem
Minimum Spanning Tree
SAT
Explanation - Program verification often requires knowing if a program halts, which is undecidable.
Correct answer is: Halting Problem
Q.15 Gödel’s incompleteness theorem is related to undecidability in:
Arithmetic
Graph Theory
Geometry
Probability
Explanation - Gödel showed that in arithmetic, there exist true statements that are undecidable within the system.
Correct answer is: Arithmetic
Q.16 Which of the following is a decidable property?
Whether a TM halts on all inputs
Whether a DFA accepts a string
Whether a TM halts on input w
Whether a language is context-free
Explanation - Checking if a DFA accepts a given string is decidable and efficient using state transitions.
Correct answer is: Whether a DFA accepts a string
Q.17 The acceptance problem for Turing Machines (ATM) is:
Decidable
Undecidable
Regular
Context-free
Explanation - ATM = {⟨M,w⟩ | M accepts w} is undecidable, proven via reduction from the Halting Problem.
Correct answer is: Undecidable
Q.18 Which of the following illustrates Rice’s theorem?
Checking if a TM accepts any string
Checking if a DFA accepts ε
Checking if a DFA is minimal
Checking if a regular expression is valid
Explanation - By Rice’s theorem, determining whether a TM’s language has a property like non-emptiness is undecidable.
Correct answer is: Checking if a TM accepts any string
Q.19 The problem of determining whether two Turing Machines accept the same language is:
Decidable
Undecidable
NP-complete
PSPACE-complete
Explanation - Language equivalence for TMs is undecidable as it generalizes the Halting Problem.
Correct answer is: Undecidable
Q.20 Which of the following problems is related to undecidability?
Tiling Problem
Knapsack Problem
Dijkstra’s Algorithm
Primality Testing
Explanation - The Tiling Problem (Domino Problem) is undecidable, as proved by Berger in 1966.
Correct answer is: Tiling Problem
Q.21 Which property is undecidable for context-free grammars?
Whether grammar generates ε
Whether grammar generates a given string
Whether grammar is ambiguous
Whether grammar is regular
Explanation - Grammar ambiguity is undecidable for context-free grammars, though membership is decidable.
Correct answer is: Whether grammar is ambiguous
Q.22 The complement of the Halting Problem is:
Decidable
Undecidable
Regular
Context-free
Explanation - Both the Halting Problem and its complement are undecidable, though one is semi-decidable.
Correct answer is: Undecidable
Q.23 Which of the following is semi-decidable but not decidable?
ATM
DFA membership problem
CFG membership problem
Regular language equivalence
Explanation - ATM is semi-decidable since if M accepts w, we can eventually verify it, but rejection cannot always be decided.
Correct answer is: ATM
Q.24 The word problem for semi-groups is:
Decidable
Undecidable
NP-complete
PSPACE-complete
Explanation - The word problem asks if two words are equivalent under semi-group relations, which is undecidable.
Correct answer is: Undecidable
Q.25 Determining if a TM accepts the empty language is:
Decidable
Undecidable
Regular
Context-free
Explanation - The emptiness problem for TMs is undecidable, as it reduces to the Halting Problem.
Correct answer is: Undecidable