F21 · Topic 3.18
Timeout is not a proof
1. Predict first
A counter starts 0 and adds 1 until reaching 101. A tool stops after 100 increments. Predict the counter and the correct result label.
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.
2. Build your procedure
Write a bounded observer with a target and step budget. Report halted only when the condition is reached; otherwise report unknown after budget.
Use AP CSP pseudocode, a language you know, or precise plain language. Your code is not executed here. Use the classroom assignment to save your response.
3. Check boundaries
| Input | Expected | Why this case |
|---|---|---|
| target0; budget10 | Halted;0steps | Initial condition already satisfied. |
| target5; budget10 | Halted;5steps | Reachable within budget. |
| target101; budget100 | Unknown after 100 steps; counter 100 | Timeout does not imply infinite execution. |
4. Explain and reflect
Why does this tool not decide whether arbitrary programs halt?
Model limits: A fixed counter model only. The tool neither accepts arbitrary programs nor decides the general halting problem.