AP CSP 3.18 Exercise 2: Undecidable Problems Applied Challenge

Big Idea 3: Algorithms and Programming · Topic 3.18 · Exercise 2

Undecidable Problems: Applied Challenge

Six questions separating hard from impossible, which is the distinction this topic exists to teach.

Back to the Topic 3.18 lessonAll Big Idea 3 topics

How this one is different

Almost every wrong answer here confuses slow with impossible. An undecidable problem is not one nobody has solved yet.

Applied Practice

6 questions · scenario driven · every answer is recorded for your teacher

Question 1 of 6Analyze
What makes a problem undecidable?
Incorrect. A slow problem is still solvable. Time is not the criterion.
Correct. Undecidability is about the non existence of any correct general algorithm, not about resources or effort.
Incorrect. A memory limit is a practical constraint, not a proof of impossibility.
Incorrect. An unsolved problem may simply be waiting for a better idea. Undecidable means proven impossible.
Question 2 of 6Evaluate
A student says the traveling salesman problem is undecidable.
What is the correct correction?
Correct. Checking every route is a correct algorithm, so the problem is decidable. Its cost is what makes it impractical.
Incorrect. Decidability is a property of a problem, not of a particular input size.
Incorrect. Every problem falls into one category or the other.
Incorrect. Lacking an efficient solution is not the same as lacking any solution.
Question 3 of 6Apply
The halting problem asks whether an arbitrary program will eventually stop on a given input. What is known about it?
Incorrect. It is not a matter of time. No algorithm exists at any cost.
Incorrect. Line count does not change the result for the general problem.
Incorrect. Waiting never distinguishes a program that will stop later from one that never will.
Correct. This is the standard example of undecidability, proven rather than merely unsolved.
Question 4 of 6Transfer
A tool claims to detect every infinite loop in any submitted program.
What can be concluded?
Incorrect. Some are easy to spot. Detecting all of them in any program is not.
Incorrect. Speed does not make an impossible guarantee possible.
Correct. The general claim is exactly the halting problem, so a real tool catches recognizable patterns and cannot be complete.
Incorrect. A heuristic that is always correct on this problem would be a solution to it, which cannot exist.
Question 5 of 6Analyze
Which pair correctly classifies the two problems?
Incorrect. This reverses both classifications.
Correct. Sorting has well known correct algorithms, and the halting problem has been proven to have none.
Incorrect. Sorting is solved routinely.
Incorrect. The halting problem is the canonical undecidable problem.
Question 6 of 6Evaluate
A student argues that faster computers will eventually make undecidable problems solvable.
What is the correct response?
Correct. The limit is mathematical rather than physical, so hardware improvements are simply the wrong axis.
Incorrect. Input size does not change the result.
Incorrect. Computers do keep getting faster. That is not why the argument fails.
Incorrect. Speed addresses how long an algorithm takes, and undecidable problems have no algorithm to speed up.

Where to go next

Rework the Topic 3.18 lesson and quiz Sit the Big Idea 3 unit test part A Sit the Big Idea 3 unit test part B

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.

Typically responds within 24 hours
✓

Message Sent!

Thanks for reaching out. I'll get back to you within 24 hours.

🏫 Welcome, fellow educator!

I offer curriculum resources, practice materials, and study guides designed for AP CS teachers. Let me know what you're looking for — whether it's classroom materials, a guest speaker, or Teachers Pay Teachers resources.

✉

Email

[email protected]

📚

Courses

AP CSA, CSP, & Cybersecurity

⏱

Response Time

Within 24 hours

Prefer email? Reach me directly at [email protected]