What are the limits of computation, and what does it mean for a problem to be undecidable?
Topic 3.18 Undecidable Problems: some problems cannot be solved by any algorithm for all inputs (undecidable problems), and some solvable problems take unreasonable time, so heuristics give approximate answers.
A focused answer to AP CSP Topic 3.18, covering decidable versus undecidable problems, the limits of computation, the difference between unsolvable and merely slow problems, reasonable versus unreasonable running time, and the role of heuristics.
Reviewed by: AI editorial process; not yet individually human-reviewed
Have a quick question? Jump to the Q&A page
Jump to a section
What this topic is asking
The College Board (Topic 3.18) wants you to understand the limits of computation. Some problems are undecidable: no algorithm can produce a correct answer for every possible input. This is different from problems that are solvable but slow, where an algorithm exists but takes unreasonable time on large inputs. For those, heuristics give approximate answers quickly. Knowing these limits is part of understanding what computing can and cannot do.
Decidable versus undecidable
Undecidable is not the same as slow
This distinction is the heart of the topic. A problem that takes a billion years to solve exactly is still decidable (an algorithm exists); it is just impractical. An undecidable problem has no correct general algorithm at all.
Reasonable versus unreasonable time
For solvable problems, efficiency matters. Reasonable running times grow polynomially with the input size and stay practical. Unreasonable running times grow exponentially and quickly become impossible to run, even on fast computers, as the input grows.
Heuristics for hard problems
A delivery company that cannot compute the exact shortest route through hundreds of stops in reasonable time uses a heuristic to find a route that is close to optimal, fast enough to be useful.
Try this
Q1. Explain the difference between an undecidable problem and a solvable problem with unreasonable running time. [2 points]
- Cue. Undecidable: no algorithm can solve it for all inputs, regardless of time. Unreasonable time: an algorithm exists but grows too fast (for example exponentially) to be practical on large inputs.
Q2. Why might a programmer use a heuristic? [1 point]
- Cue. To get a good-enough approximate answer quickly when computing the exact answer would take unreasonable (for example exponential) time.
Exam-style practice questions
Practice questions written in the style of College Board exam questions on this dot point, with worked answer explainers. The year tag is the paper they imitate, not the source.
AP 2022 (style)1 marksMultiple choice. Which statement best describes an undecidable problem?
(A) A problem that takes a very long time but can always be solved.
(B) A problem for which no algorithm can give a correct yes-or-no answer for every possible input.
(C) A problem that only computers, not humans, can solve.
(D) A problem with too much input data to store.
Show worked answer →
The answer is (B).
An undecidable problem is one for which no algorithm exists that produces a correct answer for every possible input; it is a fundamental limit of computation, not a matter of speed. (A) describes a solvable-but-slow problem (unreasonable time), which is different. (C) and (D) are unrelated distractors about who solves it or storage.
Markers reward distinguishing undecidable (no algorithm exists for all inputs) from merely slow (an algorithm exists but takes unreasonable time).
AP 2021 (style)2 marksFree response (short). Explain the difference between a problem that is undecidable and a problem that is solvable but takes an unreasonable amount of time. Give why a heuristic might be used for the second kind.
Show worked answer →
A 2-point question on the limits of computation.
Point 1: An undecidable problem has no algorithm that solves it for all inputs, no matter how much time is available. A solvable-but-slow problem does have an algorithm, but the algorithm's running time grows so fast (for example exponentially) that it is impractical for large inputs.
Point 2: For the slow-but-solvable case, a heuristic gives an approximate, good-enough answer quickly instead of the exact answer, trading guaranteed optimality for practical speed. A common error is to call a slow problem undecidable.
Related dot points
- Topic 3.11/3.17/3.18 Binary Search and Efficiency: binary search finds a value in a sorted list far faster than linear search, and algorithms are compared by efficiency, with some problems being unsolvable or only approximable.
A focused answer to AP CSP Topics 3.11, 3.17 and 3.18, covering linear versus binary search, why binary search needs a sorted list, reasonable versus unreasonable running time, polynomial versus exponential growth, heuristics, and undecidable problems.
- Topic 3.9 Developing Algorithms: an algorithm is a finite set of instructions that accomplishes a task, built by combining sequencing, selection and iteration, and different algorithms can solve the same problem.
A focused answer to AP CSP Topic 3.9, covering what an algorithm is, the three building blocks (sequencing, selection, iteration), expressing algorithms in pseudocode and language, that different algorithms can solve the same problem, and standard list algorithms.
- Topic 3.15/3.16 Random Values and Simulations: simulations are simplified, abstract models of real phenomena that often use random values to represent variability, trading detail for speed, safety and repeatability.
A focused answer to AP CSP Topics 3.15 and 3.16, covering the RANDOM procedure and generating random values, what a simulation is, why simulations are abstractions, their advantages and limitations, and using randomness to model variability, with worked pseudocode.
- Topic 3.10 Lists: a list is an ordered collection of elements accessed by index; AP CSP lists are 1-indexed and support traversal and modification with APPEND, INSERT and REMOVE.
A focused answer to AP CSP Topic 3.10, covering lists as ordered collections, 1-based indexing in AP CSP pseudocode, accessing elements, traversing with FOR EACH and REPEAT, list operations (APPEND, INSERT, REMOVE, LENGTH), and why lists scale data processing.
- Topic 3.8 Iteration: iteration (REPEAT n TIMES and REPEAT UNTIL) repeats a block of code, with the number of repetitions controlled by a count or a condition.
A focused answer to AP CSP Topic 3.8, covering REPEAT n TIMES and REPEAT UNTIL loops in AP CSP pseudocode, counting iterations, accumulating values, infinite loops and off-by-one errors, and tracing loop execution.
Sources & how we know this
- AP Computer Science Principles Course and Exam Description — College Board (2025)