AP CSP Topic 3.18 Coding Practice - Undecidable Problems

Big Idea 3: Algorithms and Programming · Topic 3.18 · Coding Practice

Undecidable Problems - Find the Boundary Yourself

No program can tell you whether every program halts. Plenty of programs can tell you whether one halts within a budget you set. That gap is the whole topic.

You sorted problems into answerable and not in Halt or Not. Now write the code that sits on the line. Nothing here simulates an undecidable problem, because nothing can. What you can run is the bounded version, and running it shows you exactly what a bound buys and what it costs: an answer every time, about a question slightly smaller than the one you asked.

Problem 1 of 4

The hailstone sequence: if a number is even, halve it; if it is odd, triple it and add one. Starting at 27, run the sequence until it reaches 1, giving up after 200 steps. Print halted after N steps with the real step count.

Expected output: halted after 111 steps

Show AP pseudocode reference
x ← 27
steps ← 0
REPEAT UNTIL(x = 1 OR steps ≥ 200)
{
  IF(x MOD 2 = 0)
  {
    x ← x / 2
  }
  ELSE
  {
    x ← 3 * x + 1
  }
  steps ← steps + 1
}
DISPLAY("halted after " + steps + " steps")
Count one step per change to x, and stop the moment x reaches 1. Note that the sequence climbs well above 27 before it comes down. Nobody has ever proved this sequence reaches 1 for every starting number, so the step cap is not decoration.

Problem 2 of 4

Exactly the same sequence from exactly the same number, but now you are only willing to wait 50 steps. If it reaches 1 print halted after N steps; if it does not, print no answer within 50 steps. Predict which one you will get before you run it.

Expected output: no answer within 50 steps

Show AP pseudocode reference
x ← 27
steps ← 0
REPEAT UNTIL(x = 1 OR steps ≥ 50)
{
  IF(x MOD 2 = 0)
  {
    x ← x / 2
  }
  ELSE
  {
    x ← 3 * x + 1
  }
  steps ← steps + 1
}
IF(x = 1)
{
  DISPLAY("halted after " + steps + " steps")
}
ELSE
{
  DISPLAY("no answer within 50 steps")
}
Same program, same input, smaller budget, different answer. That is the point. The sequence from 27 does eventually reach 1, so "no answer within 50 steps" is not a claim that it never halts. It is a statement about your patience, not about the program.

Problem 3 of 4

Search for something that might not be there. Every even number above 2 is believed to be the sum of two primes, but nobody has proved it. Check every even number from 4 to 1000. If you find one that is not the sum of two primes, print it; if you check them all and find none, print no counterexample found up to 1000.

Expected output: no counterexample found up to 1000

Show AP pseudocode reference
FOR EACH n IN [4, 6, 8, ..., 1000]
{
  found ← false
  FOR EACH a IN [2..n]
  {
    IF(isPrime(a) AND isPrime(n - a))
    {
      found ← true
    }
  }
  IF(NOT found)
  {
    DISPLAY(n)
  }
}
DISPLAY("no counterexample found up to 1000")
You will need a small prime test: a number is prime if nothing from 2 up to its square root divides it. The result is the lesson. Checking a thousand numbers and finding nothing is evidence, not proof, and no matter how high you raise the limit it never becomes proof.

Problem 4 of 4

Write from scratch. Build a bounded halting decider. The program under test starts at x = 1 and doubles until x is greater than 500. Decide whether it stops within 100 steps, and print either yes, it halts in N steps or no, still running after 100 steps.

Expected output: yes, it halts in 9 steps

Show AP pseudocode reference
x ← 1
steps ← 0
REPEAT UNTIL(x > 500 OR steps ≥ 100)
{
  x ← x * 2
  steps ← steps + 1
}
IF(x > 500)
{
  DISPLAY("yes, it halts in " + steps + " steps")
}
ELSE
{
  DISPLAY("no, still running after 100 steps")
}
This decider always answers, on any program you hand it, because it can only ever run 100 steps before giving up. That is what makes the bounded question decidable. Drop the bound and ask "does it halt at all" and no such decider can exist, for any language, ever. Not undiscovered, proved impossible.

Your code runs on a secure external service. Answers are checked automatically and nothing is stored.

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]