Skip to topic
    ← Back to course topics

    Halting problem — AQA A-Level Computer Science

    The Halting problem asks whether a general algorithm can determine if an arbitrary computer program will finish running or continue indefinitely on a given input. Alan Turing proved in 1936 that no such universal algorithm can exist, demonstrating that there are absolute theoretical limits to what computers can compute.

    Halting problem explained

    This statement asks you to describe the Halting problem without proving it.

    Read the full explanation

    The Halting problem asks whether there is a general procedure that, given any program and a particular input, can determine whether that program will eventually halt, that is, stop, or run forever. The question is about the general case: you are asked to decide for every program and every input, not just for one. The problem is unsolvable, meaning no algorithm exists that always gives the correct yes or no answer for all program and input pairs. You should describe the problem clearly, naming the two possible outcomes, halting and non-halting, and stating that the decider must work for any program supplied. You are not required to give Turing's proof, so do not spend time reproducing it. A concise, accurate description with the phrase 'for any program and input' secures the key content.

    Your focus

    1. Describe the Halting problem (but not prove it), that is the unsolvable problem of determining whether any program will eventually stop if given particular input.

    Which command word is this?

    Give a concise, precise fact or definition without elaboration (e.g., state whether the Halting problem is decidable).

    Halting problem exam tips

    Topic Overview

    The Halting problem is a foundational problem in theoretical computer science, introduced by Alan Turing in 1936. It asks whether it is logically possible to design a general algorithm that, given any computer program and an arbitrary input, can accurately predict whether the program will finish executing or run forever in an infinite loop.

    Turing proved that such an algorithm is mathematically impossible using proof by contradiction and a self-referential construction. This outcome is significant within AQA A-Level Computer Science because it establishes that not all well-defined problems are computable, setting the absolute theoretical boundary for what automated computing machines can achieve.

    Key Concepts
    • →Decidability: A decision problem is decidable if an algorithm can be constructed that always terminates with a correct Yes or No answer for every instance.
    • →Undecidability / Non-computability: The Halting problem is undecidable, proving that some problems can never be solved by an algorithm.
    • →Proof by Contradiction: Turing assumed a halting algorithm existed and showed that running a modified self-referential version on itself led to a logical impossibility.
    • →Turing Machine Equivalence: Because any modern computer can be modelled by a Universal Turing Machine, the impossibility applies universally to all existing and future programming languages and computers.
    Marking Points
    • States that the problem asks whether a given program will eventually stop when run on a particular input
    • Specifies that the decision must apply to any program and any input
    • Identifies the two outcomes as halting and running forever
    • States that no general algorithm can solve the problem for all cases
    Examiner Tips
    • 💡Use the phrase 'for any program and input' to show the general nature of the problem
    • 💡Name both outcomes, halting and running forever, to show full understanding
    • 💡Describe rather than prove, keeping the answer focused and accurate
    • 💡Memorise the definition of the Halting problem verbatim: 'Determining whether an arbitrary program will halt on a given input or run indefinitely.'
    • 💡Ensure you explicitly state that Turing used 'proof by contradiction' when questions ask about methodology.
    • 💡Remember that the consequence of the Halting problem is that automated debuggers cannot be built to detect all possible infinite loops in arbitrary source code.
    Common Mistakes
    • Describes the problem as checking whether a program contains errors; correct this by focusing on whether it stops
    • Limits the question to one specific program; correct this by stating that it applies to any program and input
    • Attempts a full proof when only a description is required; correct this by keeping the answer to a clear description
    • Thinking that the problem remains unsolved simply due to current technology limits: Students sometimes believe quantum computers or faster processors will one day solve it; in reality, it is logically impossible.
    • Assuming no program can ever be proven to halt: Code without loops or recursion clearly halts; Turing showed that no single program can decide the outcome for ALL programs.
    • Conflating non-computable with intractable: Intractable problems (like the Travelling Salesperson Problem) have algorithmic solutions that take unreasonable time, whereas non-computable problems have no algorithm whatsoever.
    Revision Plan
    1. 1Day 1-2: Master the exact definitions of computability, decidability, and the Halting problem.
    2. 2Day 3-4: Work through the logic of Turing's proof by contradiction (the 'Opposite/Negator' program scenario) until you can sketch it from memory.
    3. 3Day 5-6: Compare and contrast non-computable problems with intractable problems to ensure terminology precision.
    4. 4Day 7: Practise AQA past exam questions covering limits of computation and mark scheme analysis.
    Exam Question Types
    • 📋Definition questions (1-2 marks): Requiring a precise statement of what the Halting problem is.
    • 📋Short-answer explanation (3-4 marks): Explaining why the problem is significant or how Turing proved its unsolvability.
    • 📋Comparison questions (2-3 marks): Differentiating between computable, intractable, and non-computable problems.
    Command Word Expectations (AQA)
    State

    Give a concise, precise fact or definition without elaboration (e.g., state whether the Halting problem is decidable).

    Explain

    Set out the reasons or mechanisms clearly, such as explaining the theoretical significance of the Halting problem to computability.

    Describe

    Provide a step-by-step account of a process, such as outlining how proof by contradiction is applied to show undecidability.

    How Students Lose Marks (Examiner Pitfalls)
    Pitfall: Confusing non-computable problems with intractable problems.
    ❌ Weak Answer (Loses Marks):The Halting problem is an intractable problem because computers take too long and do not have enough memory to simulate an infinite loop.
    Example improved answer:The Halting problem is non-computable (undecidable). Alan Turing proved that no general algorithm can ever be written to solve it for all possible inputs, regardless of available time, memory, or processing power.
    Examiner Tip: Use the exact term 'non-computable' or 'undecidable'. Never refer to the Halting problem as simply 'intractable' or 'NP-hard', as these terms denote problems that are solvable in theory but require exponential or super-polynomial time.
    Pitfall: Stating that it is impossible to determine whether ANY program halts.
    ❌ Weak Answer (Loses Marks):You can never tell if a computer program will stop running.
    Example improved answer:It is often possible to determine whether specific programs halt on specific inputs (for example, a simple linear sequence of instructions). The Halting problem proves that no universal algorithm exists that can correctly decide the outcome for all arbitrary program-input pairs.
    Examiner Tip: Always specify that the unsolvability applies to a 'universal' or 'general' algorithm acting on 'any arbitrary program and input'.
    Step-by-Step Worked Solutions

    Question: Explain the significance of the Halting problem for the theory of computation. [3 marks]

    1. 1.Step 1: Define the core nature of the problem (it is unsolvable/undecidable).
    2. 2.Step 2: Connect this to the capability of Turing machines and modern computers.
    3. 3.Step 3: Conclude regarding the limits of computation.
    Final Answer: The Halting problem proves that there are problems that cannot be solved algorithmically (they are non-computable or undecidable). Because a Turing machine represents the theoretical limits of any digital computer, this establishes that computers cannot solve every mathematically valid problem, regardless of computational resources.

    Question: Outline the proof by contradiction used by Alan Turing to show that the Halting problem is undecidable. [4 marks]

    1. 1.Step 1: State the initial hypothesis that a general decision program exists.
    2. 2.Step 2: Describe the construction of an inverted/adversarial program that uses this decision algorithm.
    3. 3.Step 3: Analyze the behaviour when the inverted program is given its own code as input.
    4. 4.Step 4: Identify the contradiction and draw the conclusion.
    Final Answer: Assume a program Halts(P, I) exists that returns True if program P halts on input I, and False if it loops. Construct a new program Opposite(P) that calls Halts(P, P): if Halts returns True, Opposite enters an infinite loop; if Halts returns False, Opposite immediately halts. If we run Opposite(Opposite), it halts if and only if Halts says it will not halt. This logical contradiction proves the initial assumption was false: no universal program Halts(P, I) can exist.
    Active Recall Memory Test
    What is the formal definition of the Halting problem?
    Key Fact: The problem of determining whether an arbitrary computer program will eventually finish running (halt) or run forever when executed with a given input.
    Is the Halting problem classified as tractable, intractable, or non-computable?
    Key Fact: It is non-computable (undecidable).
    What method of proof did Alan Turing use to show that a universal halting checker cannot exist?
    Key Fact: Proof by contradiction.
    Why can an IDE not provide a foolproof tool that detects all infinite loops in arbitrary programs?
    Key Fact: Because doing so requires a general solution to the Halting problem, which is mathematically impossible.
    Frequently Asked Questions
    Why is the Halting problem undecidable?
    The Halting problem is undecidable because assuming a solution exists leads to an unavoidable logical contradiction. If a program could tell whether any code halts, you could construct an adversarial program that loops if the checker says it halts, and halts if the checker says it loops. Passing this adversarial program to itself forces the checker to give an answer that is simultaneously right and wrong, proving that no such checker can exist.
    Does the Halting problem mean we cannot detect infinite loops at all?
    No, it does not mean infinite loops can never be found. Compilers and static analysers regularly detect obvious infinite loops, such as 'while(true)'. The Halting problem specifically proves that you cannot write a single algorithm that is guaranteed to correctly classify every possible program and input combination without fail.
    What is the difference between an intractable problem and the Halting problem?
    An intractable problem is solvable in theory by an algorithm, but any known algorithm takes exponential time or resources as input size increases, making it practically unusable for large inputs. In contrast, the Halting problem is non-computable; no algorithm can ever be written to solve it, regardless of how much time or computational power is provided.
    Why does Turing use a Turing machine rather than a real computer to prove the problem?
    A Turing machine is a formal mathematical model of computation that captures the operational essence of any programmable computer. By proving that a Universal Turing Machine cannot solve the Halting problem, the conclusion applies unconditionally to all physical digital computers, past, present, and future.
    Can artificial intelligence or quantum computing solve the Halting problem?
    No, neither AI nor quantum computers can solve the Halting problem. AI systems run algorithms on classical or quantum architectures, and quantum computers are still bounded by the Church-Turing thesis regarding what is computable. The barrier is a fundamental logical impossibility, not a limitation of hardware or intelligence.