AP CSP topic 3.18
Undecidable Problems
A decision problem has a yes-or-no answer, like "is this number even?" A problem is decidable if an algorithm can always give the correct answer for every input. Some problems are undecidable: no algorithm can ever solve them for all inputs. The classic example is the halting problem, which asks whether any given program will eventually stop. A specific case might still be solvable even when the general problem is not.
Undecidable Problems vocabulary
- Decision problem: A problem with a yes-or-no answer.
- Decidable: Solvable by an algorithm that gives a correct answer for every input.
- Undecidable: Impossible for any algorithm to answer correctly for all inputs.
- Halting problem: Deciding whether any program will stop running; proven undecidable.
AP-style practice questions
Try each one, then open the answer. To save your progress, take this quiz in the interactive course.
1. Which of the following best describes an undecidable problem?
- (A) A problem that takes a long time to solve
- (B) A problem for which no algorithm can give a correct yes-or-no answer for every input
- (C) A problem with more than one correct answer
- (D) A problem that has not been solved yet
Show answer
(B) A problem for which no algorithm can give a correct yes-or-no answer for every input Undecidable means no algorithm can solve all cases, no matter how much time it has.
2. Which of the following problems is known to be undecidable?
- (A) Deciding if a number is even
- (B) Deciding if a list is sorted
- (C) Deciding if any given program will eventually stop running
- (D) Deciding if a word appears in a sentence
Show answer
(C) Deciding if any given program will eventually stop running The halting problem is the classic undecidable problem.
3. Which of the following is an example of a decision problem?
- (A) Find the largest number in a list
- (B) Is 91 a prime number?
- (C) Sort these names alphabetically
- (D) Display a list of colors
Show answer
(B) Is 91 a prime number? A decision problem has a yes-or-no answer.
4. A problem is undecidable. Which of the following is still possible?
- (A) An algorithm can answer it correctly for some specific inputs
- (B) An algorithm can answer it correctly for every input
- (C) A faster computer will solve every case
- (D) The problem will become decidable with more data
Show answer
(A) An algorithm can answer it correctly for some specific inputs Some instances may be solvable even though no algorithm works for all inputs.