AP Computer Science Principles Flashcards: Undecidable Problems
Written by AP Content Team, Verified for 2026 AP Exams, Last updated: May 2026
Review key ideas with interactive flashcards. This set includes 10 cards to help you master important concepts.
What type of answer is an algorithm for a decision problem expected to provide?
The algorithm is expected to provide a correct yes-or-no answer.
Card 1 of 10
All Flashcards (10)
What type of answer is an algorithm for a decision problem expected to provide?
The algorithm is expected to provide a correct yes-or-no answer.
Why do undecidable problems exist in computer science?
They exist because for certain problems, it is impossible to construct a single algorithm that can always provide a correct yes-or-no answer for every possible input.
Can an algorithm solve any part of an undecidable problem?
Yes, an undecidable problem may have some specific instances that have an algorithmic solution, but no single algorithm can solve all instances.
What is an undecidable problem?
An undecidable problem is one for which no algorithm can be constructed that is always capable of providing a correct yes-or-no answer for all instances.
The question "Is the number even?" is an example of what type of problem and why?
It is an example of a decidable problem because an algorithm can be written to produce a correct yes-or-no answer for all number inputs.
What is a decidable problem?
A decidable problem is a decision problem for which an algorithm can be written to produce a correct output for all inputs.
If a programmer writes code that solves a famous problem for a million specific inputs but cannot solve it for all inputs, what kind of problem is it likely to be?
This is characteristic of an undecidable problem, where some instances are solvable but no general algorithm exists for all instances.
What is the requirement for an algorithm to be considered a solution for a *decidable* problem?
The algorithm must be able to produce a correct output for all possible inputs, not just some of them.
What is the fundamental limitation of algorithms when faced with an undecidable problem?
The limitation is that no algorithm can be constructed that is *always* capable of providing a correct yes-or-no answer for every instance of the problem.
What is the key difference in algorithmic solvability between decidable and undecidable problems?
A decidable problem has an algorithm that solves all instances, whereas an undecidable problem has no algorithm that can solve all instances.