1. Which technique allows a Turing machine to simulate any other Turing machine with an arbitrary input?
a) Multitape Turing machine
b) Multihead Turing machine
c) Universal Turing machine
d) Multidimensional Turing machine
Answer: c) Universal Turing machine
Explanation: A Universal Turing machine is capable of simulating any other Turing machine with any arbitrary input. It serves as a fundamental concept in computability theory.
2. What property distinguishes a Multihead Turing machine from a standard Turing machine?
a) It has multiple tapes
b) It has multiple read/write heads
c) It has multiple dimensions
d) It can solve NP-complete problems
Answer: b) It has multiple read/write heads
Explanation: A Multihead Turing machine is equipped with multiple read/write heads, allowing it to perform multiple operations simultaneously on its tape(s).
3. Which type of Turing machine is capable of operating in multiple dimensions?
a) Multitape Turing machine
b) Multihead Turing machine
c) Multidimensional Turing machine
d) Universal Turing machine
Answer: c) Multidimensional Turing machine
Explanation: A Multidimensional Turing machine operates in multiple dimensions, allowing it to traverse and manipulate data in more than one direction.
4. NP-complete problems are a subset of which class of problems?
a) P
b) NP
c) NP-hard
d) Decidable
Answer: c) NP-hard
Explanation: NP-complete problems are a subset of NP-hard problems, meaning they are at least as hard as the hardest problems in NP.
5. Which class of languages includes those for which there exists an algorithm to determine whether a given input is in the language?
a) Decidable languages
b) Undecidable languages
c) Recursively enumerable languages
d) NP-complete languages
Answer: a) Decidable languages
Explanation: Decidable languages are those for which there exists an algorithm (Turing machine) that can determine whether any given input string belongs to the language.
6. What distinguishes recursively enumerable languages from decidable languages?
a) Recursively enumerable languages have an algorithm to determine membership
b) Decidable languages can be enumerated
c) Recursively enumerable languages include all NP-complete problems
d) Decidable languages are a subset of recursively enumerable languages
Answer: b) Decidable languages can be enumerated
Explanation: Recursively enumerable languages can be enumerated by a Turing machine, whereas decidable languages not only can be enumerated but also have an algorithm to determine membership.
7. Which of the following is an example of an undecidable language?
a) The set of all prime numbers
b) The set of all even numbers
c) The set of all palindromes
d) The set of all Turing machines that halt on all inputs
Answer: d) The set of all Turing machines that halt on all inputs
Explanation: The halting problem is an example of an undecidable language, meaning there is no algorithm that can determine whether an arbitrary Turing machine halts on all inputs.
8. What problem is considered the canonical example of an undecidable problem in computer science?
a) The Traveling Salesman Problem
b) The Post Correspondence Problem
c) The Knapsack Problem
d) The Graph Coloring Problem
Answer: b) The Post Correspondence Problem
Explanation: The Post Correspondence Problem is a classic example of an undecidable problem, proven by reduction from the halting problem.
9. Which problem is the Post Correspondence Problem closely related to?
a) Graph Isomorphism Problem
b) Set Cover Problem
c) Boolean Satisfiability Problem
d) Integer Factorization Problem
Answer: a) Graph Isomorphism Problem
Explanation: The Post Correspondence Problem and the Graph Isomorphism Problem are both examples of NP-complete problems, demonstrating the computational complexity of these tasks.
10. What is the central question addressed by the halting problem?
a) Whether a Turing machine can solve all computational problems
b) Whether a Turing machine can halt on any input
c) Whether a Turing machine can operate without any errors
d) Whether a Turing machine can simulate other Turing machines
Answer: b) Whether a Turing machine can halt on any input
Explanation: The halting problem asks whether there exists an algorithm that can determine, given a description of a Turing machine and an input, whether the machine will eventually halt or continue running indefinitely.
11. Which of the following is true regarding NP-complete problems?
a) They can be solved in polynomial time
b) They are a subset of NP-hard problems
c) They are always decidable
d) They are trivial to solve
Answer: b) They are a subset of NP-hard problems
Explanation: NP-complete problems are a subset of NP-hard problems, indicating they are at least as hard as the hardest problems in NP.
12. Which statement accurately describes the relationship between NP-complete and NP problems?
a) All NP problems are NP-complete
b) All NP-complete problems are also NP
c) NP-complete problems are easier than NP problems
d) NP-complete problems can be solved in polynomial time
Answer: b) All NP-complete problems are also NP
Explanation: NP-complete problems are a subset of NP problems, meaning they are contained within the set of problems for which solutions can be verified in polynomial time.
13. Which of the following problems is NP-complete?
a) Sorting a list of integers
b) Finding the shortest path in a graph
c) Traveling Salesman Problem
d) Finding the square root of a number
Answer: c) Traveling Salesman Problem
Explanation: The Traveling Salesman Problem is a classic example of an NP-complete problem, demonstrating the computational complexity of finding the shortest route that visits a set of cities and returns to the original city.
14. What distinguishes NP-complete problems from NP problems?
a) NP-complete problems have no known solution
b) NP-complete problems are solvable in polynomial time
c) NP-complete problems are a subset of NP problems
d) NP-complete problems have non-deterministic solutions
Answer: c) NP-complete problems are a subset of NP problems
Explanation: NP-complete problems are a subset of NP problems, meaning they are among the hardest problems in NP.
15. Which problem is used to demonstrate the undecidability of certain properties of formal languages?
a) The Halting Problem
b) The Traveling Salesman Problem
c) The Post Correspondence Problem
d) The Graph Coloring Problem
Answer: a) The Halting Problem
Explanation: The Halting Problem demonstrates the undecidability of certain properties of formal languages by showing that there is no algorithm that can determine whether an arbitrary Turing machine halts on all inputs.
16. Which class of problems includes those for which a solution can be verified in polynomial time?
a) P
b) NP
c) NP-complete
d) NP-hard
Answer: b) NP
Explanation: NP (nondeterministic polynomial time) includes decision problems for which a proposed solution can be verified in polynomial time, although finding the solution may not be polynomial time.
17. What does NP stand for in computational complexity theory?
a) Nondeterministic Polynomial
b) Not Possible
c) Nearest Possible
d) Non-Polynomial
Answer: a) Nondeterministic Polynomial
Explanation: NP stands for Nondeterministic Polynomial, referring to the class of decision problems for which a proposed solution can be verified in polynomial time.
18. Which of the following is a property of NP-hard problems?
a) They are easy to solve
b) They are a subset of NP-complete problems
c) They can be solved in polynomial time
d) They are at least as hard as the hardest problems in NP
Answer: d) They are at least as hard as the hardest problems in NP
Explanation: NP-hard problems are those for which any problem in NP can be reduced to them in polynomial time, indicating they are at least as hard as the hardest problems in NP.
19. Which problem demonstrates that not all decision problems can be solved algorithmically?
a) The Traveling Salesman Problem
b) The Halting Problem
c) The Post Correspondence Problem
d) The Graph Coloring Problem
Answer: b) The Halting Problem
Explanation: The Halting Problem demonstrates that there are certain decision problems for which no algorithm can exist to solve them, providing a limit to what can be computed algorithmically.
20. What is the key characteristic of undecidable languages?
a) They can be verified in polynomial time
b) They can be enumerated by a Turing machine
c) They have no algorithm to determine membership
d) They are always NP-complete
Answer: c) They have no algorithm to determine membership
Explanation: Undecidable languages are those for which there is no algorithm (Turing machine) that can determine whether any given input string belongs to the language.