Specialty Digest

Global English editionLearners’ Study Dashboard — in development
The Knowledge Library for All

Online Courses / University Track / Computing Foundations

Module 8 · Lesson 3 · Core

The limits of computing

Distinguish easy, hard and impossible problems and explain what is meant by the halting problem.

  • 50 minutes
  • Serves O8
  • Assumes Module 5 and M8.L2

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 problemWhat is known
EasyA fast method exists, such as binary search
Hard in practiceMethods exist but their cost grows too fast, such as checking every subset
Impossible in generalNo 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?

  1. The halting problem shows no general method can decide this for all programs. (1 mark)
  2. The tool may work for restricted cases. (1 mark)
  3. Ask what class of programs it covers and what it does when it cannot decide. (1 mark)
  4. 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:

2. Turing showed that:

3. A method that checks every subset fails on large inputs because:

4. A practical response to a hard problem is to:

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

MistakeWhy it fails
Thinking impossible means no program can ever be checkedIt means no general method for all programs.
Assuming faster computers solve exponential problemsA few more items cancel the gain.
Believing a promise of perfect checkingAsk about its limits.

Limits. This lesson states the main idea in words; the proof is part of later study in the theory of computation.