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
- 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
- 1Day 1-2: Master the exact definitions of computability, decidability, and the Halting problem.
- 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.
- 3Day 5-6: Compare and contrast non-computable problems with intractable problems to ensure terminology precision.
- 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)
Give a concise, precise fact or definition without elaboration (e.g., state whether the Halting problem is decidable).
Set out the reasons or mechanisms clearly, such as explaining the theoretical significance of the Halting problem to computability.
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)
Step-by-Step Worked Solutions
Question: Explain the significance of the Halting problem for the theory of computation. [3 marks]
- 1.Step 1: Define the core nature of the problem (it is unsolvable/undecidable).
- 2.Step 2: Connect this to the capability of Turing machines and modern computers.
- 3.Step 3: Conclude regarding the limits of computation.
Question: Outline the proof by contradiction used by Alan Turing to show that the Halting problem is undecidable. [4 marks]
- 1.Step 1: State the initial hypothesis that a general decision program exists.
- 2.Step 2: Describe the construction of an inverted/adversarial program that uses this decision algorithm.
- 3.Step 3: Analyze the behaviour when the inverted program is given its own code as input.
- 4.Step 4: Identify the contradiction and draw the conclusion.