Existence of undecidable problems in computing (College Board AP® Computer Science Principles): Revision Note
Decidable and undecidable problems
What is a decidable problem?
A decidable problem is one where an algorithm exists that can always produce a correct yes/no answer for every possible input
The algorithm is guaranteed to terminate (finish running) and give the correct answer in a finite number of steps
Example: "Is the number n even?" is decidable because dividing by 2 and checking the remainder always gives a definitive answer
What is an undecidable problem?
An undecidable problem is one where no algorithm can be constructed that will always produce a correct yes/no answer for every possible input
It is mathematically proven that certain problems cannot be solved by any algorithm in all cases
Example: the halting problem, which asks "Given a program and an input, will the program eventually stop or run forever?" is undecidable
The halting problem
The halting problem is the most well-known undecidable problem in computer science
No algorithm can correctly determine, for all possible programs and inputs, whether a given program will halt or loop infinitely
This is not a limitation of current technology; it is a fundamental mathematical impossibility
Partial solutions
Although undecidable problems cannot be solved in all cases, partial solutions may exist
Programmers can write algorithms that solve specific instances of an undecidable problem correctly, even though a general solution covering all possible inputs is impossible
Problem type | Can an algorithm always solve it? | Example |
|---|---|---|
Decidable | Yes, for every possible input | "Is n even?" |
Undecidable | No, not for all possible inputs | "Will this program halt?" |
Examiner Tips and Tricks
The key distinction in exam questions is that undecidable does not mean "hard to solve"; it means no algorithm can ever be written that solves it correctly for all inputs.
For the CPT, undecidable problems are unlikely to appear directly, but understanding decidability helps you reason about what your program can and cannot guarantee in your written response.
Worked Example
Which of the following best describes an undecidable problem?
(A) A problem that takes too long to solve with current computers
(B) A problem that no algorithm can solve correctly for all possible inputs
(C) A problem that requires exponential time to solve
(D) A problem that has not yet been solved by researchers
[1]
Answer:
(B) A problem that no algorithm can solve correctly for all possible inputs [1 mark]
Undecidable means it is mathematically impossible to construct an algorithm that produces the correct yes/no answer for every input; it is not simply that a solution has not been found yet
Unlock more, it's free!
Join the 100,000+ Students that ❤️ Save My Exams
the (exam) results speak for themselves:
Was this revision note helpful?
