AP® Computer Science Principles review sheet from Aim for Five (aimforfive.com/csp/units/3/3-18)
Unit 3 · Topic 3.18
3.18 Undecidable Problems
Some problems can't be solved by any algorithm at all, no matter how fast the computer. This topic covers decidable and undecidable problems and how undecidable differs from merely slow.
Key terms
- decision problem
- decidable problem
- undecidable problem
- instance of a problem
Decision problems
A decision problem is a question with a yes-or-no answer for each input. "Is this list sorted?" and "Is this number a multiple of 3?" are decision problems.
A decision problem is decidable if there's an algorithm that gives the correct yes-or-no answer for every possible input. "Is this list sorted?" is decidable. This procedure answers it correctly for any list, including empty and one-element lists:
PROCEDURE isSorted(aList)
{
i ← 1
REPEAT UNTIL (i ≥ LENGTH(aList))
{
IF (aList[i] > aList[i + 1])
{
RETURN(false)
}
i ← i + 1
}
RETURN(true)
}
It compares each element with the next one. If any pair is out of order, it returns false right away; if it gets through every pair, it returns true. isSorted([2, 5, 5, 9]) returns true and isSorted([2, 9, 5]) returns false.
Undecidable problems
An undecidable problem is a decision problem for which no algorithm can ever be written that always gives a correct yes-or-no answer. This isn't about computers being too slow or programmers not being clever enough. It has been proven that no such algorithm can exist.
Undecidable doesn't mean every instance is hopeless. Some specific inputs may still be answerable by an algorithm. What's impossible is one algorithm that answers correctly for all inputs.
The best-known example, which you won't be tested on by name, is deciding whether any given program will eventually stop or run forever. A tool can answer for many specific programs (a program with no loops clearly stops), but it's been proven that no algorithm can answer correctly for every program and input. You also won't be asked to prove or decide that a particular problem is undecidable.
Why it matters
Undecidable problems put a hard limit on what software can promise. For example, no program can perfectly check every other program for every possible bug, so programmers still rely on testing, tracing and careful design (1.4).
Undecidable versus unreasonable
These are easy to mix up, so keep them separate:
| Kind of problem | Can an algorithm solve it? | Example |
|---|---|---|
| Decidable, reasonable time | Yes, efficiently | Is this list sorted? |
| Solvable but unreasonable time | Yes, but too slowly for large inputs | Checking every possible route through many cities |
| Undecidable | No algorithm works for all inputs | Will any given program eventually stop? |
Worked examples
Try each one yourself first, then open the solution.
- Example 1
Decidable or not?
A student claims: "An undecidable problem is one that takes too long to solve, so a powerful enough computer could solve it." Explain what's wrong with this claim.
Show the solutionHide the solution
- Step 1: A problem that takes too long is still solvable; it runs in an unreasonable amount of time (3.17). Faster hardware or more time would eventually give an answer.
- Step 2: An undecidable problem has no algorithm that gives a correct answer for every input. The limit isn't speed; no such algorithm can exist at all.
- Step 3: So more computing power doesn't help with an undecidable problem.
Answer: Undecidable doesn't mean slow. It means no algorithm can always give the correct answer, so no computer, however powerful, can solve every instance.
- Example 2
Trace the decision algorithm
Using
isSortedabove, how many times does the IF condition get checked forisSorted([1, 4, 2, 8]), and what is returned?Show the solutionHide the solution
- Step 1: LENGTH is 4. i = 1: is 1 ≥ 4? No. Check aList[1] > aList[2]: 1 > 4 is false. i becomes 2.
- Step 2: i = 2: 2 ≥ 4 is false. Check 4 > 2: true, so RETURN(false) runs immediately.
- Step 3: The IF condition was checked twice.
Answer: The IF is checked 2 times and the procedure returns false.
Common mistakes
- Confusing undecidable with unreasonable time. Slow problems can be solved; undecidable ones can't be solved for every input by any algorithm.
- Thinking an undecidable problem has no solvable instances. Some instances can be solved; no single algorithm handles all of them.
- Calling a problem undecidable just because nobody has written a program for it yet.
On the exam
- Expect definition-based questions: which statement about undecidable problems is true, or what makes a problem decidable. Watch for answer choices that confuse undecidable with slow.
Connected topics
Videos
Check yourself
3 questions on 3.18 Undecidable Problems. Pick an answer to see if you got it, and why.
Which of the following best describes an undecidable problem?
Which statement about undecidable problems is true?
Which of the following is a decidable problem?
0 of 3 answered