AQA A-Level Computer Science (7517)

## Learning Outcomes

- Define the halting problem precisely using a program-input pair
- Explain why the halting problem is a non-computable, undecidable decision problem
- Distinguish between decidable, recognisable, and non-computable problems
- Describe the main idea of Turing's contradiction proof without unnecessary formal detail
- Explain why halting can sometimes be determined for specific programs but not by one general algorithm
- Apply the halting problem to exam questions about the limits of computation

## AQA A-Level Computer Science (7517) Syllabus

For the AQA A-Level Computer Science (7517), you are expected to understand the halting problem as part of the limits of computation, with a focus on the following syllabus points:

![Halting problem for a program-input pair, with outcomes of halting or infinite execution and the absence of a general deciding algorithm.](https://static.pastpaperhero.com/images/aqa-a-level-computer-science-7517-theory-of-computation-the-halting-problem_00.png)

_Program-input pairs in the halting problem yield either termination or non-termination, and no universal decider exists for all cases._

- Know that the halting problem asks whether a given program with a given input will halt or run forever
- Understand that the halting problem is an example of a non-computable or undecidable problem
- Explain that no algorithm can correctly decide halting for all possible program-input pairs
- Identify the significance of the halting problem for theory of computation
- Distinguish between a problem that is impossible in general and one that is only difficult or slow to solve
- Recognise the link between the halting problem and Turing machines as a model of computation
- Understand that some specific programs can be shown to halt, even though the general problem is unsolvable

## Test Your Knowledge

_Attempt these questions before reading this article. If you find some difficult or cannot remember the answers, look more closely at that area during your revision._

1. What is the halting problem?
2. Why is the halting problem not the same as an intractable problem?
3. What is the difference between a decidable problem and a recognisable problem?
4. Why does the halting problem show that there are limits to what computers can do?
5. What is the role of self-reference in the usual proof that the halting problem is undecidable?

## Introduction

In AQA A-Level Computer Science, the halting problem is one of the clearest examples of the limits of computation. Students often meet many algorithms that can always produce an answer if given enough steps. The halting problem matters because it shows that this is not true for every problem. Some tasks are not just slow or impractical. They are impossible to solve with a general algorithm.

The key question is simple to state: if you are given a program and an input, can you work out whether that program will eventually stop or continue forever, without just letting it run forever? Alan Turing showed in **1936** that no general algorithm can do this for every possible case.

> **Key Term: halting problem**
> The problem of deciding, for any given program and input, whether the program will eventually stop running or continue forever.

### What the halting problem is actually asking

The wording of the halting problem can look simple, but exam answers often lose marks by being too vague. It is not asking whether some programs halt. Clearly, many do. It is asking whether there exists a single correct method that works for **all** possible programs and **all** possible inputs.

A useful way to state it is:

- input 1: a program, or formally a Turing machine
- input 2: data for that program
- required output: **yes** if the program halts, **no** if it runs forever

So this is a **decision problem** because the answer is yes or no.

> **Key Term: decision problem**
> A problem where each input has a yes/no answer.

For example, consider this simple pseudocode:

```text
x ← 1
WHILE x > 0
  x ← x + 1
ENDWHILE
```

For ordinary integer arithmetic, `x` stays greater than 0, so the loop never ends. In this case, a human can inspect the code and say it does not halt.

Now consider:

```text
INPUT n
WHILE n ≠ 1
  IF n MOD 2 = 0
    n ← n / 2
  ELSE
    n ← 3n + 1
  ENDIF
ENDWHILE
```

For many values of `n`, this appears to stop, but proving what happens for every possible input is much harder. The halting problem asks for a universal method that always gets the right answer, even for cases far more complicated than this.

This is why the phrase **program-input pair** matters. The same program may halt for one input and run forever for another. A correct answer must refer to both the program and its input, not the program alone.

> **Key Term: program-input pair**
> A specific program together with a specific input value or input data set, treated as one instance of a problem.

A second source of confusion is the difference between "hard" and "impossible". Some problems take a very long time but are still computable. The halting problem is stronger than that. It is not just very expensive in time or memory. There is no algorithm that solves it in general.

> **Test Tip:** In a definition question, include all three parts: a given program, a given input, and the need to decide whether it halts or runs forever. If you miss one of these, your answer is incomplete.

### Decidable, recognisable and non-computable

To understand why the halting problem matters, you need to place it in the right category.

A problem is **decidable** if there exists an algorithm that always halts and always gives the correct yes/no answer for every input. In other words, the solver itself never gets stuck forever.

> **Key Term: decidable problem**
> A decision problem for which there is an algorithm that always halts and always gives the correct answer for every input.

A problem is **undecidable** if no such algorithm exists. That means there is no general decider for all cases.

> **Key Term: undecidable problem**
> A decision problem for which no algorithm can always halt and give the correct answer for every possible input.

In AQA language, undecidable problems are often described as **non-computable**.

> **Key Term: non-computable problem**
> A problem for which no algorithmic solution exists that can solve all instances correctly.

Students often treat "undecidable" and "recognisable" as opposites, but they are different ideas. A problem is **recognisable** if yes-instances can be confirmed in finite time, even though some no-instances may cause the algorithm to run forever.

For the halting problem, imagine this method:

1. Take the program and input.
2. Simulate the program on that input.
3. If the program stops, output **yes**.
4. If the program never stops, the simulator also never stops.

This means halting is recognisable: if the answer is yes, you can eventually see that. But if the answer is no, you may wait forever.

> **Key Term: recognisable problem**
> A problem where all yes-instances can be accepted in finite time, but some no-instances may cause the algorithm to run forever.

This gives an important distinction:

- **decidable**: always halts with yes or no
- **recognisable**: always halts for yes, but may loop forever for no
- **undecidable/non-computable**: no decider exists for all cases

Another distinction that examiners like is **rejecting** versus **looping forever**. If a machine rejects, it has still halted and given an answer. If it loops forever, it has given no answer at all.

Why does this matter? Because students sometimes write "if the machine does not accept, it rejects". That is false. There is a third possibility: it never halts.

Suppose a Turing machine is given an input string:

- it may enter an accepting state and stop
- it may enter a rejecting state and stop
- it may continue moving forever and never halt

The halting problem is built around this third possibility.

> **Test Tip:** If asked to compare recognisable and decidable, do not say both always produce an answer. Only deciders always halt on every input.

### Why no general halting tester can exist

The full formal proof is beyond what you need to reproduce in detail, but the core idea is examinable and very useful. It is a proof by contradiction using self-reference.

Start by assuming that a perfect program exists. Call it `HALT(P, x)`.

This imaginary program takes:

- `P`: a program
- `x`: an input to that program

and returns:

- `true` if `P` halts on input `x`
- `false` if `P` runs forever on input `x`

Now build a new program `D(P)` that uses `HALT` in a contrary way.

Pseudocode:

```text
PROCEDURE D(P)
  IF HALT(P, P) = true THEN
    WHILE true
    ENDWHILE
  ELSE
    STOP
  ENDIF
ENDPROCEDURE
```

Now work through what `D` does:

- It asks whether program `P` halts when run on itself as input.
- If `HALT` says yes, then `D` deliberately loops forever.
- If `HALT` says no, then `D` stops immediately.

This setup creates the contradiction when we run `D(D)`.

Case 1: suppose `HALT(D, D)` says **true**.  
That means `D(D)` should halt. But by the code above, if `HALT(D, D)` is true, then `D(D)` loops forever. Contradiction.

Case 2: suppose `HALT(D, D)` says **false**.  
That means `D(D)` should run forever. But by the code above, if `HALT(D, D)` is false, then `D(D)` stops immediately. Contradiction again.

Both possibilities fail. So the original assumption must be wrong. A perfect universal `HALT` program cannot exist.

This proof works because of two linked ideas:

- **self-reference**: the program is applied to itself
- **contradiction**: each possible answer causes the opposite result
  > **Key Term: proof by contradiction**
  > A method of proof where you assume something is true, show that this leads to an impossible result, and therefore conclude the assumption was false.
  >
  > **Key Term: self-reference**
  > A situation where a program, statement, or construction refers to itself.

Sometimes this is linked to **diagonalisation**, a method used in computability theory to build a case that escapes any proposed complete list or tester.

> **Key Term: diagonalisation**
> A method used in computability proofs where a construction is designed to differ from every case in a supposed complete method or list.

For AQA, you do not need a university-level formal proof. But you do need the logic: assume a universal halting decider, build a machine that does the opposite when analysed, apply it to itself, and obtain a contradiction.

A common mistake is to say "we cannot test whether a program halts because we would have to wait forever". That is only part of the story. The stronger claim is that no general algorithm can solve all cases correctly, even in theory.

### Significance, examples and exam traps

The halting problem matters because it proves there are limits to computation. Computer science is not only about writing faster algorithms. It is also about recognising that some problems have no general algorithmic solution at all.

This has several consequences.

First, it separates **intractable** from **unsolvable** problems. An intractable problem may have a correct solution, but the time needed grows so badly that it becomes impractical. The travelling salesman problem is a standard example of this kind of issue in school-level study. A heuristic may give an approximate answer. By contrast, the halting problem is not about approximation or speed. No amount of better hardware, more RAM, or extra time can produce a universal decider.

Second, it explains why tools such as compilers, static analysers and virus scanners can help but cannot be perfect general halting detectors. They often work well for restricted patterns. They can prove that some loops definitely terminate, or flag code that looks suspicious. But they cannot solve the halting question correctly for every possible program in every language and every input.

For example, a static analyser might see this:

```text
FOR i ← 1 TO 10
  OUTPUT i
NEXT i
```

It can safely conclude the loop halts.

It might also see this:

```text
WHILE true
  OUTPUT "running"
ENDWHILE
```

Again, it can conclude it never halts.

But for more complicated code involving user input, recursion, generated code, or simulation of other programs, no universal method can always succeed.

Third, the halting problem shows why Turing machines matter. A Turing machine is a formal model of computation. If a task cannot be solved by a Turing machine, then it is treated as non-computable in the standard model of what algorithms can do.

> **Key Term: Turing machine**
> A theoretical model of computation consisting of a tape, a read/write head, a finite set of states, and transition rules.

This is why exam answers often say the halting problem applies to both "programs" and "Turing machines". The informal and formal versions are expressing the same idea.

Students also need to avoid four common errors.

1. Confusing undecidable with unknown.  
   The halting problem is not unsolved because nobody has yet found the right algorithm. It has been proved that no such general algorithm exists.

2. Confusing non-computable with very slow.  
   If a problem takes millions of years but still has an algorithm, it is still computable. The halting problem is stronger: no universal algorithm exists.

3. Forgetting the word "general".  
   You can show halting for many specific programs. What is impossible is one method that works for every program-input pair.

4. Treating "does not halt" as "rejects".  
   Non-halting means no answer is produced, not that the answer is automatically no.

How might this appear in an exam?

A short question may ask:

- "What is meant by the halting problem?"
- "State why the halting problem is significant."
- "Explain why the halting problem is undecidable."

For a 2-mark definition, give the precise yes/no form. For a significance question, connect it to the limits of computation and the existence of non-computable problems. For an explanation question, mention assumption of a perfect tester, construction of a contrary self-referential program, and contradiction.

> **Test Tip:** For significance, do not just write "it is hard". Better phrasing is: "It proves that some problems are undecidable, so there are limits to what algorithms and computers can compute."

## Key Point Checklist

_This article has covered the following key knowledge points:_

- The halting problem asks whether a given program on a given input will halt or run forever
- It is a decision problem because the required answer is yes or no
- The halting problem is undecidable, meaning no algorithm can decide all cases correctly while always halting
- In AQA terms, it is a non-computable problem
- A decidable problem has an algorithm that always halts and always gives the correct answer
- A recognisable problem can confirm yes-instances in finite time, but may run forever on some no-instances
- The halting problem is recognisable but not decidable
- Rejecting an input is different from looping forever; one halts with an answer, the other gives no answer
- Turing's proof uses contradiction and self-reference
- The contradiction comes from assuming a perfect halting tester and then constructing a program that does the opposite
- The result applies to a general algorithm for all program-input pairs, not to every individual program analysis
- The halting problem shows that there are fundamental limits to computation

## Key Terms and Concepts

- halting problem
- decision problem
- program-input pair
- decidable problem
- undecidable problem
- non-computable problem
- recognisable problem
- proof by contradiction
- self-reference
- diagonalisation
- Turing machine


Theory of Computation - The halting problem