AP Computer Science Principles Practice Quiz: Undecidable Problems
Written by AP Content Team, Verified for 2026 AP Exams, Last updated: May 2026
Test your understanding with short quizzes. This quiz has 10 questions to check your progress.
Question 1 of 10
All Questions (10)
A) A problem that can be solved for some, but not all, inputs.
B) A problem for which an algorithm can be written to produce a correct output for all inputs.
C) A problem that has no clear yes-or-no answer.
D) A problem that is too difficult for current computers to solve.
Correct Answer: B
The text explicitly states, 'A decidable problem is a decision problem for which an algorithm can be written to produce a correct output for all inputs'.
A) It is a problem for which some instances have an algorithmic solution.
B) It is a problem that takes an extremely long time to solve.
C) It is a problem for which no algorithm can be constructed that provides a correct yes-or-no answer for all instances.
D) It is a problem that has never been solved by a computer.
Correct Answer: C
The text defines an undecidable problem as 'one for which no algorithm can be constructed that is always capable of providing a correct yes-or-no answer'.
A) The programmer has proven the halting problem is decidable.
B) The programmer's algorithm is flawed because it should work for all programs if it works for any.
C) This is consistent with the problem being undecidable, as some instances may have an algorithmic solution.
D) The problem is decidable, but the programmer's algorithm is simply incomplete.
Correct Answer: C
The text states, 'An undecidable problem may have some instances that have an algorithmic solution, but there is no algorithmic solution that could solve all instances of the problem.' The scenario described fits this definition perfectly.
A) Because it only applies to numbers.
B) Because the answer is always a simple 'yes' or 'no'.
C) Because an algorithm (checking for a remainder of 0 when divided by 2) exists that solves it for all possible integer inputs.
D) Because it can be solved quickly by a computer.
Correct Answer: C
A problem is decidable if an algorithm can be written to produce a correct output for ALL inputs. The modulo operator provides such an algorithm for checking if a number is even.
A) Decidable problems have a finite number of solutions, while undecidable problems have an infinite number.
B) A universal algorithm exists for all instances of a decidable problem, whereas no such universal algorithm exists for an undecidable problem.
C) Decidable problems can be solved by computers, while undecidable problems can only be solved by humans.
D) Decidable problems always run quickly, while undecidable problems always run slowly.
Correct Answer: B
The core difference lies in the existence of a single, universally applicable algorithm. Decidable problems have one that works for all inputs; undecidable problems do not, even if specific instances can be solved.
A) It is impossible to find a solution for any specific instance of the problem.
B) A solution might be found for a specific instance, but no single algorithm can guarantee a solution for all instances.
C) Any solution found for a specific instance must be incorrect.
D) The problem was likely misidentified as undecidable if any instance can be solved.
Correct Answer: B
The provided text explicitly clarifies this nuance: 'An undecidable problem may have some instances that have an algorithmic solution, but there is no algorithmic solution that could solve all instances of the problem.'
A) The algorithm works for every possible input without exception.
B) The algorithm works for a specific, limited subset of the problem's instances.
C) The algorithm uses a new type of supercomputer that was not previously available.
D) The algorithm can find an approximate, but not always correct, answer for all inputs.
Correct Answer: B
Undecidability means no algorithm can solve ALL instances. It does not preclude the existence of an algorithm that can solve SOME instances. Therefore, a claim to solve a subset of the problem is plausible.
A) It is a problem for which no all-encompassing algorithm can be created.
B) It is a problem that can never be solved for any specific case.
C) It is a type of decision problem.
D) It may have algorithmic solutions for some of its instances.
Correct Answer: B
The text explicitly states that an undecidable problem MAY have solutions for some instances. Therefore, the statement that it can NEVER be solved for any specific case is incorrect.
A) There are problems that are impossible for any computer to solve for all general cases.
B) All problems in computer science will eventually be solved with more powerful computers.
C) Computer science has not yet found the right algorithms for the hardest problems.
D) Every decision problem has at least one instance that cannot be solved.
Correct Answer: A
The concept of undecidability establishes that there are inherent logical limits to what can be computed. It's not a matter of processing power or finding a clever algorithm; for undecidable problems, a general algorithmic solution is proven to be impossible.
A) Decidable, because an algorithm exists that solves almost all instances.
B) Undecidable, because no algorithm exists that can solve ALL instances.
C) Decidable, because the algorithm is mostly correct.
D) Undecidable, because the algorithm is flawed.
Correct Answer: B
The definition of a decidable problem requires an algorithm that produces a correct output for ALL inputs. If it is proven that no algorithm can cover that final 0.1% of cases, then the problem is undecidable, regardless of how many cases can be solved.