Limits of computation — AQA A-Level Computer Science
Limits of computation explores what algorithms can and cannot theoretically solve, distinguishing between computable and uncomputable problems as well as tractable and intractable complexities. It covers foundational concepts including Turing's Halting problem, polynomial versus exponential time complexity, and the role of heuristic methods.
Limits of computation explained
This statement asks you to be aware that two separate factors limit what a computer can calculate.
Read the full explanation
The first is algorithmic complexity: an algorithm whose running time grows very quickly with input size, such as O(2ⁿ), becomes impractical even for moderate n. For example, if each operation takes one microsecond, an O(2ⁿ) algorithm with n = 60 would need about 2⁶⁰ microseconds, roughly 36,000 years, so the problem is effectively uncomputable in practice even though a solution exists. The second factor is hardware: finite processing speed, finite memory and finite precision in storing numbers mean that very large inputs, very large numbers or required storage can exceed what a machine can handle. Together these explain why some problems are infeasible to solve exactly for large inputs and why programmers choose efficient algorithms and suitable data representations.
Your focus
- Be aware that algorithmic complexity and hardware impose limits on what can be computed.
Which command word is this?
Set out purposes or reasons using precise technical definitions (e.g. defining intractable by referencing polynomial vs exponential growth and practical time limits).
Limits of computation exam tips
Topic Overview
The limits of computation topic examines the theoretical boundaries of what computers can solve regardless of future advancements in hardware. It distinguishes between solvable problems that can be solved in practical time, problems that can theoretically be solved but take an unreasonable duration, and problems that can never be computed by any algorithm.
Understanding these boundaries allows computer scientists to classify problem difficulty, deploy heuristic approximations for intractable challenges like scheduling or logistics, and appreciate the foundational work of Alan Turing regarding decidability.
Key Concepts
- →Computable vs Uncomputable: Computable problems can be solved by an algorithm, whereas uncomputable (undecidable) problems cannot be solved algorithmically for all inputs.
- →Tractable vs Intractable: Tractable problems have polynomial time complexity (e.g. O(n), O(n log n), O(n^k)) and can be solved in reasonable time; intractable problems have exponential (O(2^n)) or factorial (O(n!)) complexity.
- →The Halting Problem: Alan Turing's mathematical proof that a general program cannot be created to decide if any arbitrary program will halt on a given input.
- →Heuristics: Problem-solving techniques that sacrifice mathematical perfection to produce good enough solutions in practical polynomial time for intractable problems.
Marking Points
- Explains that algorithmic complexity limits computation when running time grows too quickly
- Gives an example of an exponential or otherwise impractical growth rate
- Explains that finite hardware limits speed, memory and numerical precision
- Links both limits to what can practically be computed for large inputs
Examiner Tips
- 💡Use an example with a specific growth rate and a rough running time to show impracticality.
- 💡Make sure your answer covers both algorithmic and hardware limits.
- 💡Explain the consequence for computation rather than only naming the limit.
- 💡Always contrast tractable with intractable using time complexity classes: polynomial time (O(n^k)) versus exponential/factorial time (O(2^n), O(n!)).
- 💡In questions about intractable problems (e.g. Travelling Salesperson), immediately identify 'heuristics' as the appropriate practical remedy.
- 💡When explaining the Halting problem, mention Alan Turing, undecidability, and proof by contradiction to ensure top-band evaluation marks.
Common Mistakes
- States that any problem can be solved given enough time; practical limits of growth rate must be considered.
- Treats hardware limits as irrelevant because modern computers are fast; finite memory and precision still restrict computation.
- Describes only one of the two limits; the statement requires both algorithmic complexity and hardware.
- Assuming intractable means impossible to solve: An intractable problem has a known algorithmic solution, but computing it for large inputs takes an infeasible amount of time. Only uncomputable problems are impossible.
- Believing heuristic algorithms always find the best solution: Heuristics deliberately trade off accuracy or optimality to achieve computational feasibility within reasonable time.
- Thinking the Halting problem means compilers cannot detect any infinite loops: Compilers can identify specific static infinite loops (e.g. while True with no break), but no single algorithm can detect it for every possible program.
Revision Plan
- 1Week 1 (Days 1-3): Master the formal definitions of computable, uncomputable, tractable, and intractable; categorise common algorithms by their Big-O efficiency.
- 2Week 1 (Days 4-5): Study the Travelling Salesperson Problem, graph-colouring, and understand how heuristic methods (e.g. A* search, genetic algorithms) offer workable solutions.
- 3Week 2 (Days 1-3): Walk step-by-step through Alan Turing's Halting problem and the proof by contradiction mechanism.
- 4Week 2 (Days 4-5): Practise past AQA A-Level Paper 1 questions focusing on the distinction between intractable and unsolvable problems.
Exam Question Types
- 📋Short definition questions: Defining tractable, intractable, or undecidable problems in terms of polynomial time and computability.
- 📋Scenario-based problem solving: Analysing an exponential algorithm (such as TSP or knapsack) and explaining why a heuristic approach is required.
- 📋Theory and significance questions: Explaining the Halting problem, how it is proved by contradiction, and its impact on computational theory.
Command Word Expectations (AQA)
Set out purposes or reasons using precise technical definitions (e.g. defining intractable by referencing polynomial vs exponential growth and practical time limits).
Explore multiple perspectives or trade-offs, such as evaluating exact exponential algorithms against heuristic approximation techniques.
Give a short, concise answer or formal definition without needing extended narrative or justification.
How Students Lose Marks (Examiner Pitfalls)
Step-by-Step Worked Solutions
Question: A delivery firm uses a brute-force algorithm to find the shortest route between n customer locations (the Travelling Salesperson Problem). The algorithm has a time complexity of O(n!). (a) Explain why this problem is described as intractable. (b) Explain how the firm could modify their algorithmic strategy to obtain practical delivery routes.
- 1.Step 1: Define what an intractable problem is in terms of algorithmic complexity. An intractable problem is one for which a theoretical algorithm exists, but the time or resources required to solve it grow too rapidly (super-polynomial, such as factorial O(n!)) to be solved in reasonable time for non-trivial values of n.
- 2.Step 2: Connect this directly to the scenario. For a small increase in customer locations (e.g. increasing from 10 to 20 cities), n! increases astronomically, requiring billions of years of compute time.
- 3.Step 3: Provide the standard solution for intractable optimisation problems. State the use of a heuristic approach.
- 4.Step 4: Explain what a heuristic method does: it finds an approximate or 'good enough' route in polynomial (acceptable) time, sacrificing absolute mathematical optimality for computational feasibility (e.g. using a Nearest Neighbour or Genetic Algorithm approach).
Question: Describe the Halting problem and explain its wider significance to theoretical computer science.
- 1.Step 1: State the formal definition of the Halting problem. It is the problem of determining whether an arbitrary program with a given input will eventually finish running (halt) or run indefinitely.
- 2.Step 2: State Alan Turing's theoretical conclusion. Alan Turing proved that no general algorithm can exist that solves the Halting problem for all possible program-input pairs.
- 3.Step 3: Explain the method of proof. It was proven by contradiction (showing that assuming such a program exists creates an inescapable logical paradox).
- 4.Step 4: Explain its significance. It establishes a fundamental limit on computation by proving that there are non-computable (undecidable) problems that cannot be solved by any Turing machine or modern computer, regardless of processing power or time.