AP CSP Topic 3.18 Guided Notes - Undecidable Problems

Big Idea 3: Algorithms and Programming · Topic 3.18 · Guided Notes (Student)

Undecidable Problems — Guided Notes

Fill these in during class or catch up here if you were absent. Print this page or work on paper — then check yourself with the CFUs on the Topic 3.18 page.

Print these notesAll CSP topics

Today’s objectives

  • Explain what a decidable problem is — a decision problem for which an algorithm produces a correct answer for ALL inputs, such as 'Is the number even?' (LO AAP-4.B)
  • Explain what an undecidable problem is — one for which no algorithm can be built that always gives a correct yes-or-no answer (LO AAP-4.B)
  • Explain that an undecidable problem may have SOME instances with an algorithmic solution, even though no single algorithm solves all instances (LO AAP-4.B)

Bell ringer

You are a 'Yes/No Machine.' Someone hands you a question, and you must publish a fixed, foolproof set of steps that ALWAYS returns the correct yes or no — for every possible input, with no guessing. Try to write such a rule for each: (A) 'Is a whole number even?' (B) 'Here is ANY set of written instructions someone could hand you — if a person starts following them, will they eventually STOP, or keep going forever?'

Write 2–4 sentences: For which question could you write a rule guaranteed correct for EVERY possible input? For which one did every rule you tried break on some case? What is fundamentally different about the second question?

01. Decidable Problems

Key Vocabulary (LO AAP-4.B)

Term Definition (write it)
Problem
Instance
Decision problem
Decidable problem
Undecidable problem

Decidable: One Rule That's Right Every Time

  • A problem is decidable when a single algorithm returns the .
  • The CED's standard example of a decidable problem is .
  • A rule that works on the inputs you tested but fails on others .

'Is the Number Even?' — An Algorithm for Every Input

isEven returns the correct yes/no for 10 — and for EVERY integer input. That total coverage is exactly what makes the problem decidable.

AP Pseudocode (what the exam tests)

PROCEDURE isEven(number)
{
  RETURN(number MOD 2 = 0)
}
DISPLAY(isEven(10))

Python (the runnable version)

def is_even(number):
    return number % 2 == 0

print(is_even(10))

Output

true

Run and edit this yourself in the coding exercises for this topic.

What Makes These Decidable?

Each row is a yes/no decision problem that IS decidable. For each, name the single algorithm that answers it correctly for every input. The test for the last column is always the same: does one rule cover ALL inputs?

Complete the empty cells.

Decision problem One algorithm that always answers it Correct for all inputs?
Is a whole number even? Return whether number MOD 2 = 0 Yes
Is a given value in this list? Yes
Is this list already sorted? Compare each element to the next; if any is out of order, answer no

Stop and think

  1. In two sentences, explain what it means for a problem to be decidable. Use the phrase 'for all inputs' and give one example.
  2. A classmate writes an algorithm for 'Is the number even?' that returns yes for 2, 4, and 6 by listing those exact numbers. Explain why this does NOT show the problem is decidable, and what a correct algorithm would do instead.
  3. 'Is there a path from town A to town B on this map?' is a decision problem. In one sentence, explain what you would need in order to call it decidable.

Answer in complete sentences. Then check yourself with the matching CFUs on the Topic 3.18 page.

02. Undecidable Problems

Undecidable: No Algorithm Can Always Be Correct

  • A problem is undecidable when .
  • Undecidable is a claim about impossibility, not difficulty, meaning .
  • The AP exam boundary is that you explain undecidable problems exist but are NOT asked to .

Undecidable Doesn't Mean Every Case Is Hopeless

Some instances ARE solvable

But no ONE algorithm solves them ALL

  • An undecidable problem may still have .
  • What is impossible for an undecidable problem is .

AP TIP: 'Undecidable' describes the whole problem, not each instance. Some instances have algorithmic solutions; the problem as a whole has none.

Watch out — “Undecidable Means the Computer Just Isn't Powerful Enough Yet”

Myth: A problem is undecidable only because today's computers are too slow or too small; a faster, bigger machine (or a smarter future programmer) would eventually make it decidable.

Explain why this is wrong:

Stop and think

  1. In your own words, explain what it means for a problem to be undecidable. Make clear it is about impossibility, not slowness.
  2. A classmate says, 'If a problem is undecidable, then a computer can never answer it for ANY input.' Correct this precisely, using the idea that some instances may have an algorithmic solution.
  3. Explain the difference between an undecidable problem and a problem that simply runs in an unreasonable amount of time. Which one still has a correct algorithm?

Answer in complete sentences. Then check yourself with the matching CFUs on the Topic 3.18 page.

Deep Dive · Beyond the AP Exam

The Two Limits of Computing

  • The 'time' wall from Topic 3.17 describes a problem that is .
  • The 'existence' wall from Topic 3.18 describes a problem that is .

Common AP Traps

Three ways Topic 3.18 loses points on the exam — one minute now, real points in May.

Undecidable ≠ slow / undiscovered — in your own words:

Some instances can still be solved — in your own words:

You explain existence, not proof — in your own words:

Undecidable Problems, in One Slide

  • A decidable problem is a decision problem (yes/no) for which one algorithm gives a correct output for ALL inputs — e.g. 'Is the number even?'.
  • An undecidable problem is one for which NO algorithm can be constructed that is always capable of a correct yes-or-no answer — a proven impossibility, not a speed limit.
  • You explain that undecidable problems EXIST; you are not asked to determine whether a given problem is undecidable.
  • An undecidable problem may have SOME instances with an algorithmic solution, but no single algorithm solves all instances.

Exit check — I can…

  • ☐  explain what a decidable problem is — one algorithm correct for all inputs, like 'Is the number even?' (LO AAP-4.B)
  • ☐  explain what an undecidable problem is — no algorithm can always give a correct yes/no answer (LO AAP-4.B)
  • ☐  explain that undecidable problems exist without being asked to determine whether a given problem is undecidable (LO AAP-4.B)
  • ☐  explain that some instances of an undecidable problem are solvable even though no single algorithm solves them all (LO AAP-4.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]