C52 · Topic 3.18 · 40 minutes · AAP-4.B
Make honest claims from bounded testing
By the end you can:
- Describe what a bounded observation actually establishes.
- Give a counterexample to a timeout-based nontermination claim.
- Use a restricted input domain in a termination argument.
Before this lesson: topics 3.8, 3.17.
- Decidable problem
- A decision problem for which an algorithm can give a correct yes/no answer for every permitted input and halt.
- Undecidable problem
- A decision problem for which no algorithm can correctly answer every permitted input and halt.
Understand
Running tests can reveal a nonterminating or failing case within a bounded setting, but passing finitely many tests is not a proof for every possible input. State the domain: a restricted family may be decidable even though a more general family is not.
A watchdog that stops execution after 100 steps is useful engineering. Its output must be “not halted within 100 steps,” not “will never halt.” Confusing these claims would misclassify a program that halts on step 101.
Worked example
Fixed program: x ← 0; REPEAT UNTIL(x = limit) {x ← x + 1}. Domain: limit is a nonnegative integer.
- limit 0:the condition is true before the body;0 iterations.
- limit 5:5 iterations reach 5.
- limit 101:still not finished after 100 iterations, but halts on the next. The bounded observation is inconclusive about nontermination.
Explore each concept
Choose a concept, change its inputs and follow the explanation. Each example models the stated rule or scenario; completing it is practice rather than evidence of mastery.
- Decidable versus impractical
- Individual versus general halting
- Restricted domain and infinite loops
Change it · step through · explain
Change an input, predict what will happen, then advance one step. Read why the state changes, reset and experiment. This fixed teaching model does not save progress or award XP.
Ready · Make a prediction
- Problem instanceis-evenWaiting
- Instance size (0–8)5Waiting
Ready to explore: A problem, an instance and a general algorithm
Why: Change an input, predict the first effect, then advance one step.
Try this: Change one input or choose another listed case. Predict the effect, reset and compare the states and governing rule.
Step through and experiment
Change it · step through · explain
Change an input, predict what will happen, then advance one step. Read why the state changes, reset and experiment. This fixed teaching model does not save progress or award XP.
Ready · Make a prediction
- Input 1100Waiting
- Input 299Waiting
Ready to experiment
Why: Predict the first change, then advance one step.
Try this: Compare budget one below the target with budget equal to the target; also try target 0.
Check a misconception
Claim: A timeout detector solves the halting problem.
It detects a resource limit. Programs that finish just after that limit are counterexamples to a nontermination claim.
Guided practice
For the stated nonnegative domain, explain why the incrementing program terminates. What changes if negative limits are allowed?
Work with a partner. Make a prediction, compare your reasoning, then identify the rule that supports your answer.
Independent transfer
Design labels for a bounded teaching tool that distinguishes a proved terminating fixed case, an obvious fixed infinite loop and an arbitrary program that timed out.
Exit check
How does restricting the input domain help make a termination argument?
Write your reasoning before comparing with a classmate. If your teacher assigned this task, submit it through My classes to save your work and receive feedback.
Check yourself
Your practice so far
Check an answer to see its rationale.