AQA 7517 4.4.4.6: Computable and non-computable problems
The free BugBot lesson that teach this point, a robot to try it on, and the past-paper questions that test it.
What it covers
The last lesson's limit was time: intractable problems can be solved, just not quickly. This lesson's limit is harder. Some problems cannot be solved by any algorithm, on any computer, however fast, given as long as you like. In 1936 Alan Turing proved that one of the most useful problems imaginable is like this.
- Computable and non-computable
- The Halting problem
- Why no halting checker can exist
- What it means in practice
Or do it in the simulator, with tasks that mark themselves
Lessons that teach it
- A6.8 Computable problems and the Halting problem Theory of computation
Non-computable problems, the Halting problem and why it cannot be solved, and what step limits can and cannot tell you.
Try it on a robot
The task from A6.8 Computable problems and the Halting problem, running here. Change the program and press Run.
The specification is AQA's own document; this page says which of our lessons teach point 4.4.4.6 and is not endorsed by the board.