C51 · Topic 3.18 · 40 minutes · AAP-4.B
Separate difficult from undecidable
By the end you can:
- Define a general terminating decision algorithm.
- Distinguish impractical finite search from undecidability.
- Explain why some instances of an undecidable problem can be answered.
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
A decision problem asks a yes/no question. It is decidable if some algorithm halts with the correct answer on every allowed input. It may still be very slow. Undecidable means no such general algorithm exists, not that no individual case can be answered.
The general halting problem asks whether any supplied program will eventually stop on a supplied input. It is undecidable. You can still show that a particular fixed-count loop stops, or that an obvious infinite loop does not.
Worked example
Compare three questions.
- Does a finite list contain 7? A traversal decides it and always finishes.
- Does any subset of a finite list sum to 100? Enumerating all subsets is finite and decidable, though it can be expensive.
- Will every arbitrary supplied program halt on its supplied input? There is no universal correct terminating decider.
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: An undecidable problem means no case can ever be solved.
Some instances are easy; what fails is one algorithm that correctly decides all allowed instances.
Guided practice
Explain why checking all 2ⁿsubsets of a finite n-element list is not evidence of undecidability.
Work with a partner. Make a prediction, compare your reasoning, then identify the rule that supports your answer.
Independent transfer
A student observes that a program has run for one hour and labels it nonterminating. Assess the evidence.
Exit check
Give the defining difference between slow and undecidable.
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.