Skip to topic
    ← Back to course topics

    Computable and non-computable problems — AQA A-Level Computer Science

    A computable problem is one for which an algorithm can be devised that solves it in a finite number of steps, whereas a non-computable problem has no general algorithmic solution for all valid inputs. In AQA A-Level Computer Science, understanding this distinction and Turing's Halting Problem reveals the fundamental theoretical limits of automated computation.

    Computable and non-computable problems explained

    This statement asks you to accept that not every problem has an algorithm that can solve it.

    Read the full explanation

    A problem is computable if some algorithm always produces a correct answer for every valid input in a finite number of steps. A problem is non-computable (undecidable) if no such algorithm exists, however much time or memory is available. The key idea is that the limit lies in computation itself, not in current hardware or programming skill. Non-computable problems are not simply hard to solve in practice; it can be proved that no general method can ever settle them for all inputs. Recognising this helps you understand why some software tasks, such as perfectly checking every possible program for a given bug, cannot be fully automated. You should be able to state the distinction clearly and explain that awareness of the limit is what the statement requires.

    Your focus

    1. Be aware that some problems cannot be solved

    Which command word is this?

    Give reasons or show cause-and-effect relationships. For computability, explain why an algorithm cannot solve a problem or how an exponential Big-O complexity causes intractability.

    Computable and non-computable problems exam tips

    Topic Overview

    Computability theory explores the ultimate boundaries of what can and cannot be solved by algorithmic computation. It categorises problems based on whether an effective algorithmic procedure can be formulated to yield a correct answer for all possible inputs in a finite amount of time.

    Within the AQA A-Level specification, students must clearly distinguish between problems that are solvable in polynomial time (tractable), problems that are theoretically solvable but practically impossible for large data sets (intractable), and problems for which no algorithm can ever exist (non-computable), most notably demonstrated by Alan Turing's Halting Problem.

    Key Concepts
    • →Computable Problem: A problem that can be solved algorithmically within a finite number of steps on a theoretical computational model such as a Universal Turing Machine.
    • →Non-Computable Problem: A problem for which no algorithm can ever be written that is guaranteed to produce a correct output for all valid inputs.
    • →The Halting Problem: The formal proof that an algorithm cannot exist to determine whether an arbitrary computer program and input will halt or run indefinitely.
    • →Tractability vs Intractability: Tractable problems can be solved in polynomial time (O(n^k)), whereas intractable problems require super-polynomial or exponential time (O(2^n) or O(n!)), necessitating heuristic approaches.
    • →Heuristics: Problem-solving techniques that sacrifice completeness or exact optimality to find a sufficiently good, practical approximation within an acceptable timeframe for intractable problems.
    Marking Points
    • States that a computable problem has an algorithm that always gives a correct result in finite time
    • States that a non-computable problem has no algorithm that can solve it for all inputs
    • Explains that the impossibility is inherent to computation, not a matter of speed or memory
    • Gives a relevant example of a problem that cannot be solved by any algorithm
    Examiner Tips
    • 💡Use precise terms such as computable, non-computable and algorithm
    • 💡Avoid saying a problem is impossible only because it is difficult
    • 💡Be ready to give one well-known example, such as the Halting problem
    • 💡In definition questions, explicitly mention that computable problems require an algorithm that runs in a 'finite number of steps'. Omitting 'finite' frequently forfeits the mark.
    • 💡When explaining the Halting Problem, always identify the inputs: the decider program must examine an 'arbitrary program' and its 'input data'.
    • 💡Link intractable problems directly to Big-O notation; state that intractable problems possess super-polynomial or exponential complexities such as O(2^n) or O(n!).
    Common Mistakes
    • Treats non-computable problems as merely very slow to solve; correct this by stating that no algorithm exists at all
    • Assumes faster computers will eventually solve every problem; correct this by noting that the limit is theoretical
    • Confuses non-computable with unsolved; correct this by distinguishing an open question from a provably unsolvable one
    • Believing that intractable problems are non-computable: An intractable problem (like the Travelling Salesperson Problem) DOES have an algorithm, but its exponential runtime makes it unfeasible for large inputs, whereas a non-computable problem has no possible algorithm.
    • Assuming that non-computable problems could eventually be solved by more powerful computers or quantum machines: Turing proven limits are mathematical truths that apply universally to all classical and quantum computing architectures.
    • Thinking that compiler warnings for infinite loops solve the Halting Problem: Compilers can identify specific, simple infinite loop patterns using static heuristics, but they cannot evaluate all arbitrary code without facing the Halting boundary.
    Revision Plan
    1. 1Week 1, Day 1-2: Master the core definitions of computable, non-computable, tractable, and intractable, creating a three-way comparison table.
    2. 2Week 1, Day 3-4: Study Turing's proof of the Halting Problem; write out the self-referential contradiction argument in your own words until you can replicate it.
    3. 3Week 2, Day 1-2: Review time complexities and investigate why heuristics (like the A* algorithm or genetic algorithms) are applied to intractable problems instead of non-computable ones.
    4. 4Week 2, Day 3-4: Complete past AQA Paper 1 exam questions involving problem classification, Halting Problem explanations, and the limits of computation.
    Exam Question Types
    • 📋Short-answer definitions (2 marks): Define what is meant by a computable problem or non-computable problem with precision.
    • 📋Classification and justification questions (3-6 marks): Categorise given real-world algorithms/problems into tractable, intractable, or non-computable and provide rigorous computational justifications.
    • 📋Halting Problem theoretical questions (4-6 marks): Explain the Halting Problem, state its significance, and outline how proof by contradiction demonstrates undecidability.
    Command Word Expectations (AQA)
    Explain

    Give reasons or show cause-and-effect relationships. For computability, explain why an algorithm cannot solve a problem or how an exponential Big-O complexity causes intractability.

    Distinguish

    Explicitly identify differences between two concepts (e.g. tractable vs intractable). You must clearly state the distinguishing criteria, such as polynomial versus super-polynomial time complexity.

    Discuss

    Explore multiple perspectives or trade-offs. Often applied to using heuristic methods for intractable problems, evaluating the balance between computational time and solution accuracy.

    How Students Lose Marks (Examiner Pitfalls)
    Pitfall: Confusing an intractable problem (e.g. Travelling Salesperson) with a non-computable problem, or claiming that non-computable problems simply require faster hardware.
    ❌ Weak Answer (Loses Marks):A non-computable problem cannot be solved because computers run out of memory or take millions of years to run the code.
    Example improved answer:A non-computable problem is one for which it is mathematically impossible to construct an algorithm that produces a correct output for all valid inputs in a finite time. In contrast, intractable problems are computable in theory, but their algorithmic complexity (such as exponential time O(2^n)) renders them practically unsolvable for large inputs.
    Examiner Tip: Always specify that non-computable problems lack an algorithm entirely, regardless of time, memory, or computing power available.
    Pitfall: Describing the Halting Problem inaccurately as simply 'a program getting stuck in an infinite loop'.
    ❌ Weak Answer (Loses Marks):The Halting Problem is when a program has a bug or infinite while loop that prevents it from stopping.
    Example improved answer:The Halting Problem is the decision problem of whether a general program H can be written that takes any arbitrary program P and its input I, and correctly determines whether P will eventually halt or execute infinitely. Alan Turing proved that no such general algorithm H can exist, demonstrating that the Halting Problem is undecidable and non-computable.
    Examiner Tip: Frame the Halting Problem as a meta-program problem: a program trying to predict the execution behaviour of another arbitrary program on an input.
    Step-by-Step Worked Solutions

    Question: Explain why the Halting Problem is non-computable using a proof by contradiction outline. (4 marks)

    1. 1.Step 1: Assume the opposite proposition: suppose a program exists, Halt(P, I), which returns True if program P halts on input I, and False if it runs forever.
    2. 2.Step 2: Construct a new hypothetical program, Paradox(P), that takes program P as both program and input, calls Halt(P, P), and inverts the result: if Halt returns True, Paradox enters an infinite loop; if Halt returns False, Paradox halts immediately.
    3. 3.Step 3: Analyze the contradiction when Paradox is passed itself as input: Paradox(Paradox). If Paradox halts, Halt(Paradox, Paradox) must have returned False, meaning Paradox should loop forever. If Paradox loops forever, Halt(Paradox, Paradox) returned True, meaning Paradox halts.
    4. 4.Step 4: Conclude that this logical impossibility proves the initial premise was false; therefore, no general algorithm Halt(P, I) can exist, proving the problem is non-computable.
    Final Answer: The assumption that a halting decider exists leads directly to a logical contradiction when passed a self-referential adversary program; thus, no general algorithm can solve the Halting Problem, proving it is non-computable.

    Question: Three computational problems are classified: (A) Sorting a 10,000-element list using Quicksort; (B) Finding the optimal route visiting 50 cities using brute force; (C) Determining whether an arbitrary user script contains an infinite loop. Classify each problem into tractable, intractable, or non-computable, and justify your classification. (6 marks)

    1. 1.Step 1: Classify Problem A: Quicksort has an average time complexity of O(n log n), which is polynomial time. This makes it tractable because it completes in practical, realistic time for realistic input sizes.
    2. 2.Step 2: Classify Problem B: Finding the optimal tour via brute force has a factorial time complexity of O(n!). Since factorial growth is super-polynomial/exponential, an exact solution exists algorithmically, but the time required grows so rapidly that it cannot be solved in realistic time for large n. This makes it intractable.
    3. 3.Step 3: Classify Problem C: Determining whether an arbitrary program terminates on any input is an instance of the Halting Problem. Alan Turing proved no algorithm can exist to solve this for all cases. This makes it non-computable.
    4. 4.Step 4: Review definitions against AQA mark scheme criteria: ensure clear use of 'polynomial time' for tractable, 'exponential/factorial complexity' for intractable, and 'no algorithm exists' for non-computable.
    Final Answer: Problem A is tractable (solvable in polynomial time, O(n log n)); Problem B is intractable (computable but computationally infeasible for large inputs due to O(n!) complexity); Problem C is non-computable (no algorithm can exist as proven by Turing's Halting Problem).
    Active Recall Memory Test
    What defines a computable problem in theoretical computer science?
    Key Fact: A problem for which an algorithm can be designed that solves every instance of the problem in a finite number of steps.
    What is the Halting Problem and who proved it was non-computable?
    Key Fact: The decision problem of whether an arbitrary program will halt on a given input or run forever; Alan Turing proved it is non-computable.
    What is the key mathematical difference between a tractable problem and an intractable problem?
    Key Fact: Tractable problems have polynomial time complexity (O(n^k)), whereas intractable problems have super-polynomial or exponential complexity (O(2^n) or O(n!)).
    Why can heuristic algorithms be applied to intractable problems but not to non-computable problems?
    Key Fact: Heuristics approximate solvable problems where an exact algorithm exists but is too slow; they cannot solve non-computable problems because no algorithm can exist even in principle.
    Frequently Asked Questions
    Can quantum computers solve non-computable problems?
    No, quantum computers cannot solve non-computable problems. While quantum algorithms (like Shor's or Grover's) can solve certain tractable and intractable problems exponentially or quadratically faster than classical computers, they are fundamentally bounded by the Church-Turing thesis. Any problem that is non-computable for a classical Turing machine is also non-computable for a universal quantum computer.
    What is the difference between an undecidable problem and a non-computable problem?
    The terms are closely related and often used interchangeably in A-Level Computer Science. Specifically, an undecidable problem is a decision problem (a problem with a binary yes/no output) that cannot be solved by an algorithm for all inputs, such as the Halting Problem. A non-computable problem is a broader term encompassing any function or calculation for which no general algorithm can be constructed.
    Why is the Travelling Salesperson Problem classified as intractable instead of non-computable?
    The Travelling Salesperson Problem (TSP) is computable because a correct algorithm exists: checking every possible permutation of routes will guarantee finding the shortest path. However, because checking every route requires O(n!) operations, the time required becomes impossibly large even for moderate values of n. Because an algorithmic solution exists, it is classified as intractable, not non-computable.
    Can modern IDEs detect infinite loops despite the Halting Problem?
    IDEs and static analysis tools can detect certain common infinite loops, such as while(true) with no break statement, by applying specific heuristic rules and pattern matching. However, they cannot detect whether any arbitrary piece of code will halt on any arbitrary input. Turing's proof shows that no compiler will ever be able to reliably identify every infinite loop without occasionally failing or hanging itself.
    Why does the definition of a computable problem insist on a finite number of steps?
    An algorithm, by formal definition, must terminate. If a procedure requires an infinite number of operations, it never outputs a final result, meaning the problem has not been solved computationally. For a problem to be considered computable, the algorithmic procedure must reach a definite conclusion for every valid input within a finite timeframe.