AP CSP Undecidable Problems
AP CSP Undecidable Problems & the Halting Problem: Complete Guide (2025‑2026)
Some problems are undecidable — no algorithm can correctly answer YES or NO for every possible input. This is not a matter of computers being too slow or having insufficient memory. It is a mathematical proof that no such algorithm can exist. The most famous example is the Halting Problem: given a program and its input, will it eventually halt (stop) or run forever? Alan Turing proved in 1936 that no algorithm can answer this correctly for all programs.
Contents
Decidable vs. Undecidable
Decidable problems have algorithms that ALWAYS work. Undecidable problems have no such algorithm — any attempt will sometimes be wrong, crash, or run forever.
For each problem, determine whether it is decidable or undecidable:
(A) Given a number n, is n divisible by 3?
(B) Given any program P, does P print ‘Hello’ at some point during its execution?
(C) Given a list, does it contain any duplicate values?
Which are decidable (algorithm always gives correct answer) and which are undecidable?
(A) Decidable: n MOD 3 = 0 always gives the correct answer. (C) Decidable: compare all pairs or use a set — algorithms exist that always work. (B) Undecidable: to know if P ever prints ‘Hello’, you might need to run P forever. If P runs indefinitely without printing, you cannot know after any finite time whether it eventually will. No algorithm can correctly decide this for all programs P.
The Halting Problem
- Input: a program P and an input I
- Question: will P eventually stop when run on I?
- Possible answers: YES (halts) or NO (runs forever)
- Seems simple: just run P and see what happens
- Problem: if P runs forever, you wait forever
- Assume a halt-checker H(P,I) exists and always works
- Construct program D that calls H on itself
- If H says D halts, make D loop forever
- If H says D loops forever, make D halt
- D’s behavior contradicts H’s answer in every case
A programmer suggests: ‘Just run the program and see if it stops. If it stops, it halts. If it doesn’t stop after 10 seconds, it probably runs forever.’
Why does this approach fail as a general algorithm?
It cannot tell the difference between ‘will never halt’ and ‘hasn’t halted yet.’ A program that takes 1 trillion years to halt would appear to run forever after 10 seconds. Any timeout value you choose will be wrong for some program. A correct algorithm must give the right answer for EVERY program — not just probably, not most of the time. Turing proved no finite timeout or heuristic approach can be made to work for all cases.
Why This Matters
- Antivirus: can this file infect my computer? (general case undecidable)
- Will this program cause a buffer overflow?
- Does this code contain an infinite loop?
- Will this function return for all inputs?
- Formal verification of all program behaviors
- Build heuristics that work for most cases
- Use conservative safe/unsafe classification
- Test known patterns of malicious behavior
- Accept false positives (flag safe things)
- Acknowledge provable limits of automation
Common Exam Pitfalls
An undecidable problem cannot be solved correctly for ALL inputs by ANY algorithm, regardless of how much time or memory is available. It is a mathematical impossibility, not a practical difficulty.
A halt-checker might correctly determine that specific programs halt. Undecidability means the algorithm fails for SOME inputs, not that it fails for all inputs.
Unreasonable time = algorithm exists but is too slow. Undecidable = no correct algorithm exists at all. These are completely different classifications.
It is decidable for SPECIFIC programs (a known finite loop halts; an obvious infinite loop doesn’t). The undecidability applies to the GENERAL case: any program, any input.
Check for Understanding
1. An undecidable problem is best defined as:
- A problem that is too slow to solve in polynomial time
- A problem for which no algorithm can correctly answer YES or NO for every possible input
- A problem that requires exponential time to solve
- A problem that only advanced computers can solve
2. The Halting Problem asks:
- How many steps does a program take to complete?
- Given a program and input, will the program eventually stop running?
- Can all programs be made to run faster?
- Does a program produce the correct output?
3. Why can’t the Halting Problem be solved by simply running the program and waiting?
- Modern computers cannot run programs fast enough.
- The program might take an infinite amount of time, making it impossible to distinguish “will never halt” from “hasn’t halted yet”.
- Running programs is too expensive computationally.
- Programs behave differently each time they run.
4. Consider: I. Some specific instances of undecidable problems can be solved correctly. II. Undecidable means the problem takes exponential time. III. The Halting Problem was proven undecidable by Alan Turing.
- I only
- I and III only
- II and III only
- I, II, and III
5. Antivirus software cannot guarantee detecting ALL malware because:
- Antivirus developers are not skilled enough.
- General malware detection reduces to the Halting Problem, which is undecidable.
- Malware always runs faster than antivirus software.
- Antivirus software is limited to scanning 1,000 files per second.
6. Which problem is decidable?
- Will this program run forever on any input?
- Does this list contain the value 42?
- Will this program ever produce incorrect output?
- Does this function return for all possible inputs?
7. What distinguishes undecidability from unreasonable time complexity?
- Undecidable problems are solved by heuristics; unreasonable problems cannot be.
- Unreasonable: an algorithm exists but is too slow. Undecidable: no correct algorithm can exist.
- Undecidable problems require more memory than unreasonable ones.
- They are the same concept expressed differently.
8. Alan Turing proved the Halting Problem undecidable using:
- A very fast computer simulation
- Experimental testing on thousands of programs
- A proof by contradiction that any proposed halt-checker leads to a logical impossibility
- Statistical analysis of program behavior
9. Which statement about undecidable problems is most accurate?
- More powerful computers will eventually make undecidable problems solvable.
- No algorithm exists that correctly solves an undecidable problem for all possible inputs.
- Undecidable problems can be solved by quantum computers.
- Undecidable problems are only theoretical and have no real-world relevance.
10. Consider a program that either: (a) halts and prints “done”, or (b) runs in an infinite loop. A student claims they can determine which case applies by running the program for 1 hour. If it doesn’t halt, they conclude it runs forever. This approach:
- Is correct — one hour is enough time for any realistic program.
- Is correct for most programs but will fail for programs that halt after more than one hour.
- Is a valid algorithm for the Halting Problem.
- Is correct because infinite loops can always be detected within 1 hour.
How the AP Exam Tests This
- Identify whether a given problem is decidable or undecidable
- Explain why the Halting Problem cannot be solved by running programs and waiting
- Distinguish undecidability from unreasonable time complexity
- I/II/III: which statements about undecidable problems are correct
- Apply the concept: explain why antivirus or code verification has fundamental limits
FAQ
Get in Touch
Whether you're a student, parent, or teacher — I'd love to hear from you.
Just want free AP CS resources?
Enter your email below and check the subscribe box — no message needed. Students get daily practice questions and study tips. Teachers get curriculum resources and teaching strategies.
Message Sent!
Thanks for reaching out. I'll get back to you within 24 hours.
Prefer email? Reach me directly at [email protected]