Skip to topic
    ← Back to course topics

    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

    1. 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
    1. 1Week 1 (Days 1-3): Master the formal definitions of computable, uncomputable, tractable, and intractable; categorise common algorithms by their Big-O efficiency.
    2. 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.
    3. 3Week 2 (Days 1-3): Walk step-by-step through Alan Turing's Halting problem and the proof by contradiction mechanism.
    4. 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)
    Explain

    Set out purposes or reasons using precise technical definitions (e.g. defining intractable by referencing polynomial vs exponential growth and practical time limits).

    Discuss

    Explore multiple perspectives or trade-offs, such as evaluating exact exponential algorithms against heuristic approximation techniques.

    State

    Give a short, concise answer or formal definition without needing extended narrative or justification.

    How Students Lose Marks (Examiner Pitfalls)
    Pitfall: Confusing intractable problems with uncomputable (or unsolvable) problems.
    ❌ Weak Answer (Loses Marks):An intractable problem is a problem that cannot be solved by a computer at all.
    Example improved answer:An intractable problem is one that theoretically has an algorithmic solution, but cannot be solved within a polynomial or reasonable timeframe as input size grows, typically having exponential (O(2^n)) or factorial (O(n!)) time complexity. In contrast, an uncomputable problem has no algorithmic solution whatsoever.
    Examiner Tip: Use the phrase 'polynomial time complexity' or 'reasonable time' when defining tractable/intractable to secure full marks.
    Pitfall: Vague explanations of why the Halting problem is undecidable, focusing on program crashes or infinite loops instead of formal computability.
    ❌ Weak Answer (Loses Marks):The Halting problem proves that computers cannot tell if code has an infinite loop because it will just freeze.
    Example improved answer:The Halting problem proves that it is impossible to write a general algorithm that can determine, for any arbitrary computer program and its input, whether the program will halt or continue running forever. Turing proved this using proof by contradiction, showing that a general halting decider leads to a logical paradox.
    Examiner Tip: Always specify that the Halting problem applies to a *general* algorithm for *any* program and input, rather than specific programs.
    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. 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. 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. 3.Step 3: Provide the standard solution for intractable optimisation problems. State the use of a heuristic approach.
    4. 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).
    Final Answer: (a) The problem is intractable because its factorial time complexity O(n!) means execution time grows so rapidly that finding an exact solution for realistic values of n takes an unreasonable length of time. (b) The firm should implement a heuristic algorithm, which sacrifices finding the absolute optimal route in order to find a near-optimal solution in polynomial/acceptable time.

    Question: Describe the Halting problem and explain its wider significance to theoretical computer science.

    1. 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. 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. 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. 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.
    Final Answer: The Halting problem asks whether an algorithm exists that can determine, for any arbitrary program and input, if that program will finish running or run forever. Turing proved that no general algorithm can solve this for all cases. Its significance is that it proves some problems are fundamentally uncomputable, demonstrating inherent limits to what computers can ever solve.
    Active Recall Memory Test
    What defines a tractable problem in terms of complexity?
    Key Fact: A problem that can be solved by a polynomial-time algorithm (e.g. O(n^k)), meaning it can be computed in a reasonable amount of time.
    What is the core conclusion of the Halting problem?
    Key Fact: It is mathematically impossible to write a general algorithm that decides whether any arbitrary program and input will halt or run forever.
    What is a heuristic method and when is it used?
    Key Fact: An approach designed to find a good enough approximation in polynomial time when finding an exact solution is computationally intractable.
    What is the difference between an intractable problem and an uncomputable problem?
    Key Fact: An intractable problem has an algorithm but takes exponential/factorial time; an uncomputable problem has no possible algorithm.
    Frequently Asked Questions
    What is the difference between an intractable problem and an unsolvable problem?
    An unsolvable (or uncomputable) problem cannot be solved by any theoretical algorithm on any computer, regardless of time or resources, such as the Halting problem. An intractable problem does have a correct algorithm, but the algorithm requires super-polynomial time (like exponential or factorial), meaning it cannot be solved in a reasonable amount of time for realistic inputs.
    Why can't supercomputers solve intractable problems?
    Supercomputers increase processing speed by constant factors, but intractable problems scale at exponential (O(2^n)) or factorial (O(n!)) rates. Even if a supercomputer is a billion times faster, adding a modest number of additional inputs will quickly multiply the required operations beyond the age of the universe.
    Why do compilers warn about infinite loops if the Halting problem is unsolvable?
    The Halting problem proves that no *general* algorithm can correctly decide halting for *all* arbitrary programs and inputs. Compilers can easily spot specific, predictable cases of non-termination (such as 'while True' loops without exit conditions) using static analysis, but they cannot evaluate every possible program structure.
    What is an example of an intractable problem in real-world computing?
    The Travelling Salesperson Problem (TSP) is a classic example. When solved using a brute-force search that checks every permutation of routes, it has a complexity of O(n!). Other examples include the Boolean Satisfiability problem (SAT) and the Knapsack problem.
    Do I need to know the mathematical proof of the Halting problem for AQA A-Level?
    You do not need to reproduce the full formal mathematical proof in detail, but you must understand the conceptual proof by contradiction: if a decider function H(program, input) existed, one could construct a paradoxical program that halts if H says it loops and loops if H says it halts, creating a logical impossibility.