Phase 1: Prepare
Step 1 Warm-up recall
From M8.L2: how many possible 3-digit passwords are there?
Private: nothing you type here is sent or stored.
Step 2 Learning goal
By the end of this lesson you can:
- separate easy, hard and impossible problems (Foundation);
- explain why exponential methods fail (Core);
- describe the halting problem in words (Core).
Phase 2: Teach
Step 3 A familiar example
Some jobs are simply quick. Some take so long that they are no use in practice. A few cannot be done by any method at all. Knowing which kind you face saves effort and avoids false promises.
Step 4 Clear explanation
Problems fall into three groups.
| Kind of problem | What is known |
|---|---|
| Easy | A fast method exists, such as binary search |
| Hard in practice | Methods exist but their cost grows too fast, such as checking every subset |
| Impossible in general | No method can solve every case; Turing showed this for the halting problem |
For hard problems, methods that check every possibility have exponential cost, as shown in Module 5, so they fail beyond small sizes. A practical response is to settle for an answer that is good enough rather than perfect, or to restrict the problem to a smaller or special case.
For the third group, Alan Turing showed in 1936 that no single method can decide, for every program and every input, whether the program will finish or run forever. This is called the halting problem. It does not mean that particular programs cannot be checked, only that no general method works for all of them. One consequence is that a tool promising to find every possible fault in every program is making a claim that cannot be fully met. Read more in the entry on Alan Turing.
Step 5 Worked example (4 marks)
A vendor claims a tool that proves every program will finish. How should you respond?
- The halting problem shows no general method can decide this for all programs. (1 mark)
- The tool may work for restricted cases. (1 mark)
- Ask what class of programs it covers and what it does when it cannot decide. (1 mark)
- Answer: treat the general claim with caution and ask about its limits. (1 mark)
Phase 3: Practise
Step 6 Learner practice (instant-marked)
1. The halting problem asks whether:
It is about deciding if a program stops.
2. Turing showed that:
There is no general method.
3. A method that checks every subset fails on large inputs because:
The cost doubles with each item.
4. A practical response to a hard problem is to:
A good answer in time can beat a perfect one never.
Phase 4: Close
Step 7 Recap
- Problems may be easy, hard in practice or impossible in general.
- Exponential methods fail on large inputs.
- The halting problem has no general method.
Step 8 Exit ticket (ungraded)
Put binary search, checking every subset and the halting problem into the three groups.
Private: nothing you type here is sent or stored.
Step 9 Go further (Extension)
Read the entry on Alan Turing and note when he published the result.
Common mistakes
| Mistake | Why it fails |
|---|---|
| Thinking impossible means no program can ever be checked | It means no general method for all programs. |
| Assuming faster computers solve exponential problems | A few more items cancel the gain. |
| Believing a promise of perfect checking | Ask about its limits. |
Limits. This lesson states the main idea in words; the proof is part of later study in the theory of computation.